Floyd-Warshall-lal O(n^3) időben megvannak a pontpárokra a legrövidebb utak, de a Dijkstra vagy Bellmann-Ford a jobb csak a fent nevezett pontokra a jobb, hiszen ez így az algoritmusra nézve csak konstans szorzót jelent, és nem n-eset. Ezek után csak ki kell választani, hogy melyik az optimális út.
Amit elsőre írtam, az az első gondolat, ha a Dijsktra és tsai "rég voltak". Hm, muszáj lesz ezeket is átnéznem.