Tag Archive: Graph

Floyd–Warshall算法简介

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

Bellman-Ford算法简介

  Bellman-Ford算法用于计算有向图中的单源最短路径。对于有V个顶点和E条边的图,Bellman-Ford的时间复杂度为O(V·E),效率低于Dijkstra算法。Bellman-Ford可以用于有负权边的情况,且能判断负权环,十分灵活。   Wiki上给出的Bellman-Ford算法的伪代码如下所示: function BellmanFord(list vertices, list …
Read more