| dbo:abstract
|
- Johnson algoritmusa lehetővé teszi a megtalálását az között egy súlyozott élekkel rendelkező irányított gráfban . Lehetőséget ad arra, hogy egyes élek súlya negatív szám legyen, de nem lehet negatív súlyozott kör. A Bellman – Ford algoritmus segítségével működik egy olyan bemeneti gráf transzformációjának kiszámításához, amely eltávolítja az összes negatív súlyt, lehetővé téve Dijkstra algoritmusának használatát a transzformált gráfon. Donald B. Johnson után nevezték el az algoritmust, aki 1977-ben publikálta a technikát. Hasonló újra-súlyozási technikát alkalmaznak Suurballe algoritmusában is, hogy két nem negatív élsúlyú grafikonon két minimális teljes hosszúságú és diszjunkt utat keressen ugyanazon két csúcs között. (hu)
- Johnson algoritmusa lehetővé teszi a megtalálását az között egy súlyozott élekkel rendelkező irányított gráfban . Lehetőséget ad arra, hogy egyes élek súlya negatív szám legyen, de nem lehet negatív súlyozott kör. A Bellman – Ford algoritmus segítségével működik egy olyan bemeneti gráf transzformációjának kiszámításához, amely eltávolítja az összes negatív súlyt, lehetővé téve Dijkstra algoritmusának használatát a transzformált gráfon. Donald B. Johnson után nevezték el az algoritmust, aki 1977-ben publikálta a technikát. Hasonló újra-súlyozási technikát alkalmaznak Suurballe algoritmusában is, hogy két nem negatív élsúlyú grafikonon két minimális teljes hosszúságú és diszjunkt utat keressen ugyanazon két csúcs között. (hu)
|
