有关最短路径的问题可以归纳为找到一个顶点到达另一个顶点的成本最小的路径。
1、单点最短路径
给定一幅加权有向图和一个起点s，回答从s到给定的目的顶点v是否存在一条有向路径。
为解决这个问题先引入如下数据结构
加权有向边：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public class DirectedEdge {
private final int v;//边的起点
private final int w;//边的终点
private final double weight;//边的权重
public DirectedEdge(int v,int w,double weight){
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight(){
return weight;
}
public int from(){
return v;
}
public int to(){
return w;
}
public String toString() {
return String.format("%d->%d %.2f",v,w,weight);
}
}
加权有向图：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91public class EdgeWeightedDigraph {
private final int V; // 顶点总数
private int E; // 边的总数
private Bag<DirectedEdge>[] adj; // 邻接表
private int[] indegree; // 顶点V的入度
public EdgeWeightedDigraph(int V) {
this.V = V;
this.E = 0;
this.indegree = new int[V];
adj = (Bag<DirectedEdge>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<DirectedEdge>();
}
public EdgeWeightedDigraph(int V, int E) {
this(V);
for (int i = 0; i < E; i++) {
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
double weight = 0.01 * StdRandom.uniform(100);
DirectedEdge e = new DirectedEdge(v, w, weight);
addEdge(e);
}
}
public EdgeWeightedDigraph(In in) {
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
double weight = in.readDouble();
addEdge(new DirectedEdge(v, w, weight));
}
}
public EdgeWeightedDigraph(EdgeWeightedDigraph G) {
this(G.V());
this.E = G.E();
for (int v = 0; v < G.V(); v++)
this.indegree[v] = G.indegree(v);
for (int v = 0; v < G.V(); v++) {
Stack<DirectedEdge> reverse = new Stack<DirectedEdge>();
for (DirectedEdge e : G.adj[v]) {
reverse.push(e);
}
for (DirectedEdge e : reverse) {
adj[v].add(e);
}
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(DirectedEdge e) {
int v = e.from();
int w = e.to();
adj[v].add(e);
indegree[w]++;
E++;
}
public Iterable<DirectedEdge> adj(int v) {
return adj[v];
}
public int outdegree(int v) {
return adj[v].size();
}
public int indegree(int v) {
return indegree[v];
}
public Iterable<DirectedEdge> edges() {
Bag<DirectedEdge> list = new Bag<DirectedEdge>();
for (int v = 0; v < V; v++) {
for (DirectedEdge e : adj(v)) {
list.add(e);
}
}
return list;
}
}
Dijkstra算法
以上图为例来简单讲解下Dijkstra算法，我们以v1为起点来研究其到其余各店的最短路径。
我们可以看到Dis数组代表了v1到其余各点的距离，无限大表示不可达。
此时最短路径中的确定数组为v1和v3，因为v1到v3距离最短并且由于权重非负，所以不可能存在经过第三点到达v3还比v1直接到v3还要短的情况。
然后观察v3，发现其与v4相连，此时v1->v3->v4为10+50=60，比v1到v4的无穷大要小，则更新Dis数组。
更新结束之后，我们需要找出dis[0]和dis[2]之外的最小距离，因为dis[0]和dis[2]都已经是确定值，我们发现dis[4]最小，而dis[4]代表v1和v5之间的距离，所以此时我们引入v5，之后就会发现v1->v5->v4的距离小于v1->v4，所以继续更新，同理，v1->v5->v6距离也小于v1->v6。
重复上述过程，即可的到最终结果
以上图片来自https://blog.csdn.net/qq_35644234/article/details/60870719
以上就是Dijkstra算法的演示过程。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53public class DijkstraSP {
private double[] distTo; // distTo[v]为从起点到v的距离
private DirectedEdge[] edgeTo; // edgeTo[v]为从起点到v的最后一条边
private IndexMinPQ<Double> pq; // 优先队列
public 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;
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);
}
}
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]);
}
}
public double distTo(int v) {
return distTo[v];
}
private boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}
分析：
上面代码中最重要的部分就在于relax方法，通过遍历距离最近元素(v)的邻接表，找出权重较小的边，如果有则更新数据，相当于“放松”了路径。
2、无环加权有向图
Dijkstra算法可以处理非负权重的有(无)环图，而如果遇到无环
加权有向图，则有更加高效的处理办法，它能够处理负权重的边，并且能在线性时间内解决单点最短路径问题。
这个算法的核心是拓扑排序，因为在入度为0的元素被选出时，每条边v->w都只会被放松一次。当v被放松时，得到distTo[w]<=distTo[v]+e.weight()，因为distTo[v]的大小不会改变，之所以不会改变是因为按照拓扑排序，该元素只可能被访问一次，所以distTo[w]只会变小，从而到达效果。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46public class AcyclicSP {
private double[] distTo;
private edu.princeton.cs.algs4.DirectedEdge[] edgeTo;
public AcyclicSP(EdgeWeightedDigraph G, int s) {
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;
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);
}
}
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;
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}
3、最长路径
在无环加权有向图中的单点最长路径问题中，只需要将distTo[]的初始值变成Double.NEGATIVE_TNFINITY，并将relax方法中的不等式方向更改即可。
4、并行任务调度
在并行任务中涉及到“关键路径”，所谓关键路径就是指在此路径下任何任务的启动延迟都会影响到整个项目的完成时间。
5、基于队列的Bellman-Ford算法
Dijkstra算法无法处理带负权重的图，这时就轮到Bellman-Ford算法来发挥作用。
Bellman-Ford算法主要是分两步来进行，第一步也是对最短路径进行求解，第二步也是关键的一步就是判断当前边集中是否存在负权重环，如果存在则表示不存在最短路径，否则边集就是最短路径。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70public class BellmanFordSP {
private double[] distTo;//从起点到某个顶点的路径长度
private DirectedEdge[] edgeTo;//从起点到某个顶点的最后一条边
private boolean[] onQ;//该顶点是否存在于队列中
private Queue<Integer> queue;//正在被放松的顶点
private int cost;//relax()的调用次数
private Iterable<DirectedEdge> cycle;//edgeTo[]中的是否有负权重环
public BellmanFordSP(EdgeWeightedDigraph G,int s){
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
onQ = new boolean[G.V()];
queue = new Queue<>();
for(int v = 0;v<G.V();v++){
distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;
queue.enqueue(s);
onQ[s] = true;
while(!queue.isEmpty()&&!hasNegativeCycle()){
int v = queue.dequeue();
onQ[v] = false;
relax(G,v);
}
}
private void relax(EdgeWeightedDigraph G,int v){
for(DirectedEdge e:G.adj(v)){
int w = e.to();
if(distTo[w]>distTo[v]+e.weight()){
distTo[w] = distTo[v]+e.weight();
edgeTo[w] = e;
if(!onQ[w]){
queue.enqueue(w);
onQ[w] = true;
}
}
if(cost++%G.V()==0)
findNegativeCycle();
}
}
public double distTo(int v) {
if (hasNegativeCycle())
throw new UnsupportedOperationException("Negative cost cycle exists");
return distTo[v];
}
public boolean hasPathTo(int v){
return distTo[v] < Double.POSITIVE_INFINITY;
}
private void findNegativeCycle(){
int V = edgeTo.length;
EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
for (int v = 0; v < V; v++)
if (edgeTo[v] != null)
spt.addEdge(edgeTo[v]);
EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
cycle = finder.cycle();
}
public boolean hasNegativeCycle(){
return cycle != null;
}
public Iterable<DirectedEdge> negativeCycle(){
return cycle;
}
}
上面代码的关键在于relax方法和findNegativeCycle方法，relax方法与之前的一致，都是判断路径是否缩短，但是此时如果路径缩短则需要将该结点入队，入队是为了防止出现重复的顶点。
这其中的缺少的数据结构可以到http://algs4.cs.princeton.edu/code 下载。