1 package package01;
2
3 import java.util.Iterator;
4 import java.util.NoSuchElementException;
5 import edu.princeton.cs.algs4.StdOut;
6 import edu.princeton.cs.algs4.StdRandom;
7 import edu.princeton.cs.algs4.DirectedEdge;
8
9 public class class01
10 {
11 private static final String NEWLINE = System.getProperty("line.separator");
12
13 private final int V;
14 private int E;
15 private DirectedEdge[][] adj;
16
17 public class01(int inputV)
18 {
19 if (inputV <0)
20 throw new IllegalArgumentException("\n V <0.\n");
21 V = inputV;
22 E = 0;
23 adj = new DirectedEdge[V][V];
24 }
25
26 public class01(int inputV, int inputE)
27 {
28 this(inputV);
29 if (inputE <0 || inputE > V*V)
30 throw new IllegalArgumentException("\n E <0 || E > V*V.\n");
31
32 for (E = 0; E != inputE;)
33 {
34 int v = StdRandom.uniform(V), w = StdRandom.uniform(V);
35 double weight = Math.round(100 * StdRandom.uniform()) / 100.0;
36 addEdge(new DirectedEdge(v, w, weight));
37 }
38 }
39
40 public int V()
41 {
42 return V;
43 }
44
45 public int E()
46 {
47 return E;
48 }
49
50 public void addEdge(DirectedEdge e)
51 {
52 int v = e.from();
53 int w = e.to();
54 if (adj[v][w] == null)
55 {
56 E++;
57 adj[v][w] = e;
58 }
59 }
60
61 public Iterable adj(int v)
62 {
63 return new AdjIterator(v);
64 }
65
66 private class AdjIterator implements Iterator, Iterable
67 {
68 private int v;
69 private int w = 0;
70
71 public AdjIterator(int inputV)
72 {
73 v = inputV;
74 }
75
76 public Iterator iterator()
77 {
78 return this;
79 }
80
81 public boolean hasNext() // 同一行里还有元素（还有以该顶点为起点的边）
82 {
83 for (; w )
84 {
85 if (adj[v][w] != null)
86 return true;
87
88 }
89 return false;
90 }
91
92 public DirectedEdge next()
93 {
94 if (!hasNext())
95 throw new NoSuchElementException();
96 return adj[v][w++];
97 }
98
99 public void remove()
100 {
101 throw new UnsupportedOperationException();
102 }
103 }
104
105 public String toString()
106 {
107 StringBuilder s = new StringBuilder();
108 s.append(V + " " + E + NEWLINE);
109 for (int v = 0; v )
110 {
111 s.append(v + ": ");
112 for (DirectedEdge e : adj(v))
113 s.append(e + " ");
114 s.append(NEWLINE);
115 }
116 return s.toString();
117 }
118
119 public static void main(String[] args)
120 {
121 int V = Integer.parseInt(args[0]);
122 int E = Integer.parseInt(args[1]);
123 class01 G = new class01(V, E);
124 StdOut.println(G);
125 }
126 }
1 package package01;
2
3 import edu.princeton.cs.algs4.StdOut;
4 import edu.princeton.cs.algs4.StdRandom;
5 import edu.princeton.cs.algs4.DirectedEdge;
6 import edu.princeton.cs.algs4.EdgeWeightedDigraph;
7 import edu.princeton.cs.algs4.EdgeWeightedDirectedCycle;
8 import edu.princeton.cs.algs4.Stack;
9 import edu.princeton.cs.algs4.AdjMatrixEdgeWeightedDigraph;
10
11 public class class01
12 {
13 private boolean hasNegativeCycle; // 是否有负环
14 private double[][] distTo; // 从 v 到 w 的最短路径记作 distTo[v][w]
15 private DirectedEdge[][] edgeTo; // 从 v 到 w 的最短路径的最后一条边记作 edgeTo[v][w]
16
17 public class01(AdjMatrixEdgeWeightedDigraph G)
18 {
19 int V = G.V();
20 distTo = new double[V][V];
21 edgeTo = new DirectedEdge[V][V];
22 for (int v = 0; v // 邻接表元素初始化为正无穷
23 {
24 for (int w = 0; w )
25 distTo[v][w] = Double.POSITIVE_INFINITY;
26 }
27 for (int v = 0; v )
28 {
29 for (DirectedEdge e : G.adj(v)) // 添加以 v 为起点的各条边
30 {
31 distTo[e.from()][e.to()] = e.weight();
32 edgeTo[e.from()][e.to()] = e;
33 }
34 if (distTo[v][v] >= 0.0) // 自环归零
35 {
36 distTo[v][v] = 0.0;
37 edgeTo[v][v] = null;
38 }
39 }
40 for (int i = 0; i // 循环 V 次
41 {
42 for (int v = 0; v // 用 0 ~ i 作为中间顶点，尝试将其引入
43 {
44 if (edgeTo[v][i] == null) // v 不可达 i，跳过
45 continue;
46 for (int w = 0; w )
47 {
48 if (distTo[v][w] > distTo[v][i] + distTo[i][w]) // 引入顶点 i 使得 v 到 w 的距离缩短
49 {
50 distTo[v][w] = distTo[v][i] + distTo[i][w]; // 正式引入顶点 i
51 edgeTo[v][w] = edgeTo[i][w];
52 }
53 }
54 if (distTo[v][v] <0.0) // 检测负环，条件是某顶点到自身的最短路径小于 0
55 {
56 hasNegativeCycle = true;
57 return;
58 }
59 }
60 }
61 }
62
63 public boolean hasNegativeCycle()
64 {
65 return hasNegativeCycle;
66 }
67
68 public Iterable negativeCycle()
69 {
70 for (int v = 0; v )
71 {
72 if (distTo[v][v] <0.0)
73 {
74 int V = edgeTo.length;
75 EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
76 for (int w = 0; w // 把与 v 有关的边加入一个含边权有向图，用类 EdgeWeightedDirectedCycle 寻找环
77 {
78 if (edgeTo[v][w] != null) // 实际上所有从 v 延伸出去的最短路径的边都加上了
79 spt.addEdge(edgeTo[v][w]);
80 }
81 EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
82 return finder.cycle();
83 }
84 }
85 return null;
86 }
87
88 public boolean hasPath(int s, int t)
89 {
90
91 return distTo[s][t] < Double.POSITIVE_INFINITY;
92 }
93
94 public double dist(int s, int t)
95 {
96 if (hasNegativeCycle())
97 throw new UnsupportedOperationException("\n Negative cost cycle exists.\n");
98 return distTo[s][t];
99 }
100
101 public Iterable path(int s, int t)
102 {
103 if (hasNegativeCycle())
104 throw new UnsupportedOperationException("\n Negative cost cycle exists.\n");
105 if (!hasPath(s, t))
106 return null;
107 Stack path = new Stack();
108 for (DirectedEdge e = edgeTo[s][t]; e != null; e = edgeTo[s][e.from()])
109 path.push(e);
110 return path;
111 }
112
113 public static void main(String[] args)
114 {
115 int V = Integer.parseInt(args[0]);
116 int E = Integer.parseInt(args[1]);
117 AdjMatrixEdgeWeightedDigraph G = new AdjMatrixEdgeWeightedDigraph(V);
118 for (int i = 0; i )
119 {
120 int v = StdRandom.uniform(V);
121 int w = StdRandom.uniform(V);
122 double weight = Math.round(100 * (StdRandom.uniform() - 0.15)) / 100.0;
123 if (v == w) G.addEdge(new DirectedEdge(v, w, Math.abs(weight)));
124 else G.addEdge(new DirectedEdge(v, w, weight));
125 }
126
127 StdOut.println(G);
128 class01 spt = new class01(G);
129 StdOut.printf(" ");
130 for (int v = 0; v )
131 StdOut.printf("%6d ", v);
132 StdOut.println();
133 for (int v = 0; v )
134 {
135 StdOut.printf("%3d: ", v);
136 for (int w = 0; w )
137 {
138 if (spt.hasPath(v, w))
139 StdOut.printf("%6.2f ", spt.dist(v, w));
140 else
141 StdOut.printf(" Inf "); // 存在负环的路径长度显示为负无穷
142 }
143 StdOut.println();
144 }
145 if (spt.hasNegativeCycle()) // 有负环单独显示，否则正常显示各条最短路径
146 {
147 StdOut.println("Negative cost cycle:");
148 for (DirectedEdge e : spt.negativeCycle())
149 StdOut.println(e);
150 StdOut.println();
151 }
152 else
153 {
154 for (int v = 0; v )
155 {
156 for (int w = 0; w )
157 {
158 if (spt.hasPath(v, w)) {
159 StdOut.printf("%d to %d (%5.2f) ", v, w, spt.dist(v, w));
160 for (DirectedEdge e : spt.path(v, w))
161 StdOut.print(e + " ");
162 StdOut.println();
163 }
164 else
165 StdOut.printf("%d to %d no path\n", v, w);
166 }
167 }
168 }
169 }
170 }
京公网安备 11010802041100号