Tag Archive: Floyd Warshall

Floyd–Warshall算法简介

  Floyd–Warshall算法用于寻找有向图中任意两点间的最短路径,即多源最短路径。该算法可用于带负权边的图,但不能用于带负权环的图。该算法需要比较每一组节点间所有的路径,时间复杂度为Θ(|V|^3)。   设有一个图G,有N个节点,编号为1,2,…,N。函数shortestPath(i, j, k) 返回当仅使用点集{1,2,…,k}为中间节点时,从节点i到达节点j…
Read more