最短路径算法总结

最短路径算法

• 给定起点的最短路径问题
• 给定终点的最短路径问题
• 给定起点和终点的最短路径，也就是求任意两点之间的最短路径问题

• `Dijkstra` //适用于无负权重
• `Topological sort` //适用于无环
• `Bellman-Ford` //适用于无负环

Dijkstra

步骤

1. 初始化所有顶点到源点的路径为无限大
2. 顶点插入优先队列
3. 出队一个点
4. 对所有与这个点相关联的边进行 `放松` 操作
5. 重复3

代码

`// @author Robert Sedgewick @author Kevin Waynepublic DijkstraSP(EdgeWeightedDigraph G, int s) {       for (DirectedEdge e : G.edges()) {           if (e.weight() < 0)               throw new IllegalArgumentException("edge " + e + " has negative weight");       }       distTo = new double[G.V()];       edgeTo = new DirectedEdge[G.V()];       for (int v = 0; v < G.V(); v++)           distTo[v] = Double.POSITIVE_INFINITY;       distTo[s] = 0.0;       // relax vertices in order of distance from s       pq = new IndexMinPQ<Double>(G.V());       pq.insert(s, distTo[s]);       while (!pq.isEmpty()) {           int v = pq.delMin();           for (DirectedEdge e : G.adj(v))               relax(e);       }   }   // relax edge e and update pq if changed   private void relax(DirectedEdge e) {       int v = e.from(), w = e.to();       if (distTo[w] > distTo[v] + e.weight()) {           distTo[w] = distTo[v] + e.weight();           edgeTo[w] = e;           if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);           else                pq.insert(w, distTo[w]);       }   }`

关于 `Dijkstra` 为什么不能含有负权值

`private void relax(DirectedEdge e) {       int v = e.from(), w = e.to();       if (distTo[w] > distTo[v] + e.weight()) {   //若是负边的话每次都会减小，就会不断进入优先队列！！！           distTo[w] = distTo[v] + e.weight();             edgeTo[w] = e;           if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);           else                pq.insert(w, distTo[w]);       }   }`

效率

`Dijkstra` 效率取决于优先队列的效率。二叉堆的话效率为 `O(ElogV)`

Topological sort

步骤

1. 初始化所有顶点到源点的路径为无限大
2. 对顶点进行 `拓扑排序`
3. 按照顶点顺序，对每条相关的边进行 `放松`

代码

`Topological topological = new Topological(G);if (!topological.hasOrder())    throw new IllegalArgumentException("Digraph is not acyclic.");for (int v : topological.order()) {    for (DirectedEdge e : G.adj(v))        relax(e);}`

效率

Topological sort algorithm computes SPT in any edgeweightedDAG in time proportional to E + V

Bellman-Ford

`for (int i = 0; i < G.V(); i++)    for (int v = 0; v < G.V(); v++)        for (DirectedEdge e : G.adj(v))            relax(e);`