Ha a mélységi keresést az x pontból indítjuk, akkor a legmagasabb szintű pontokba futó utak az x pontból induló leghosszabb utak, ez következik abból, hogy a gráf minden pontja a faváz egy elodje és utódja között fut (lásd az eloző feladatot). Egy ilyen út megtalálásához elegendő tehát (lényegében) p(n) lépés. Ha minden pontra megcsináljuk ezt, akkor legfeljebb np(n) lépésben megkapjuk minden pontból a leghosszabb utat, s ezek közül a leghosszabb(ak) lesz(nek) a gráf leghosszabb útja(i).
| TARTALOMJEGYZÉK |