„Gráfelméleti fogalomtár” változatai közötti eltérés

Egy '''súlyozott gráf'''ban a gráf minden éléhez egy számértéket rendelünk, ezt hívjuk az él ''súly''ának. Az élsúlyok legtöbbször [[valós szám]]ok, de adott esetben szorítkozhatunk csak racionális vagy egész számokra is. Náhány algoritmus még további megszorításokat követel, mint például a [[Dijkstra algoritmus]], amely csak pozitív (akár nemnegatív) élsúlyok esetén működik jól. Egy '''út súlya''', vagy egy '''fa súlya''' azőtaz őt alkotó élek összsúlya. Néha egy nemlétező élet (anti-él) egy végtelen ∞ súlyú éllel helyettesítünk. Szokás '''költség'''nek is hívni a súlyt; de előfordul a ''hossz'' fogalmának félrevezető használata is, ui. egy út hossza súlyozatlan gráfban az éleinek száma, nem pedig összsúlya. Egy gráfról általában feltehető, hogy ''súlyozatlan'', de bármely súlyozatlan gráfra gondolhatunk egy olyan súlyozott gráfként, melyben minden él súlya egységnyi 1.