Floyd algoritmusa - verem túlcsordulása oroszul
Igazából két kérdésem van ezen az algoritmuson, remélem, hogy segít. 1) A grafikon szomszédsági mátrix van állítva, meg kell találni csúcsok, amelyek között van egy tetszőlegesen kis távolságra (azaz, vannak ciklusok negatív súly). Itt van egy kód:
d - szomszédsági mátrix, INF = 1e1000, a tömb kell egy rekordot, ha a kettes i és j közötti van egy tetszőlegesen kis utat.
A kód nem működik megfelelően, mi a hiba? Ezt az anyagot használtam:
A grafikonban vannak negatív súlyszámú ciklusok.
Ebben az esetben tetszőleges rövid út lehet néhány csúcspár között. Nem, ezek a párok egyszerűek a "legrövidebb" utak mátrixán, a Floyd algoritmussal konstruálva. Vannak állítások:
Ha van egy súlya a negatív ciklus áthaladó vertex i, akkor Ai, i kisebb mint 0. párja között a csúcsok (i, j) van egy tetszőlegesen kis utat, ha, és csak akkor, ha létezik egy útvonal a i-től j, a ciklus, amely tartalmaz negatív súlyokat, vagy más szóval, létezik egy csúcsot k olyan, hogy van egy út a i k, a k j, és van egy ciklus a negatív tömeg áthaladó k
2) Meg kell találni a legmagasabb elérési utakat az összes csúcspár között. Ezt próbáltam: töltöttem a függőségi mátrixot a bemeneti távolságokkal szemben, és a következő kódot használtam:
Nincs értelme. Milyen hibáim vannak?
A munka után Floyd algoritmus a mátrixban d i minden egyes vertex eltárolt minimum úthossz az egyes vertex J = 1..n (n - a csúcsok száma). Ezért az első kérdésre adott válasz:
A válasz a második kérdésre adandó vagy ki kell írni a szomszédsági mátrix ellenzék értékeket, vagy módosíthatja a jel> az if (d [i] [j]> d [i] [k] + d [k] [j]) a védjegyet <, но не два варианта вместе, иначе получается тоже самое, что и поиск минимального пути :).