public class AllPairsShortestPathDemo
1: //AllPairsShortestPathDemo.java
3: import java.util.ArrayList;
4: import java.util.Collection;
5: import java.util.Comparator;
6: import java.util.HashSet;
7: import java.util.List;
8: import java.util.PriorityQueue;
10: public class AllPairsShortestPathDemo
11: {
12: // Implementation of Floyd-Warshall all-pairs shortest path
13: public static double[][] allPairsShortestPath
14: (
15: List<Vertex> vertices,
16: List<Edge> edges
17: )
18: {
19: int numVertices = vertices.size();
21: // Initialize distMatrix to a numVertices x numVertices matrix
22: // with all values set to infinity
23: double[][] distMatrix = new double[numVertices][numVertices];
24: for (int i = 0; i < numVertices; i++)
25: {
26: for (int j = 0; j < numVertices; j++)
27: {
28: distMatrix[i][j] = Double.POSITIVE_INFINITY;
29: }
30: }
32: // Set each distance for vertex to same vertex to 0
33: for (int i = 0; i < numVertices; i++)
34: {
35: distMatrix[i][i] = 0.0;
36: }
38: // Finish matrix initialization
39: for (Edge edge : edges)
40: {
41: int index1 = vertices.indexOf(edge.fromVertex);
42: int index2 = vertices.indexOf(edge.toVertex);
43: distMatrix[index1][index2] = edge.weight;
44: }
46: // Loop through vertices
47: for (int k = 0; k < numVertices; k++)
48: {
49: for (int toIndex = 0; toIndex < numVertices; toIndex++)
50: {
51: for (int fromIndex = 0; fromIndex < numVertices; fromIndex++)
52: {
53: double currentLength = distMatrix[fromIndex][toIndex];
54: double possibleLength =
55: distMatrix[fromIndex][k] + distMatrix[k][toIndex];
56: if (possibleLength < currentLength)
57: {
58: distMatrix[fromIndex][toIndex] = possibleLength;
59: }
60: }
61: }
62: }
64: return distMatrix;
65: }
67: public static void displayMatrix(double[][] matrix, List<Vertex> vertices)
68: {
69: // This method assumes a simple square matrix, where each entry is
70: // either an integer in the range [-99, 99], or infinity. Each vertex's
71: // label is also assumed to be a single character.
73: // First print column headers
74: System.out.printf(" ");
75: for (int entryIndex = 0; entryIndex < matrix.length; entryIndex++)
76: {
77: System.out.printf(" %s ", vertices.get(entryIndex).label);
78: }
79: System.out.println();
81: for (int rowIndex = 0; rowIndex < matrix.length; rowIndex++)
82: {
83: System.out.printf("%s [ ", vertices.get(rowIndex).label);
84: for (int entryIndex = 0; entryIndex < matrix.length; entryIndex++)
85: {
86: double entry = matrix[rowIndex][entryIndex];
88: // Case 1: entry is infinity
89: if (Double.isInfinite(entry))
90: {
91: System.out.print("inf ");
92: }
94: // Case 2: entry is negative
95: else if (entry < 0)
96: {
97: // Case 2A: entry is > -10
98: if (entry > -10)
99: {
100: System.out.printf("%d ", (int)entry);
101: }
102: // Case 2B: entry is <= -10
103: else
104: {
105: System.out.printf("%d ", (int)entry);
106: }
107: }
109: // Case 3: entry is non-negative
110: else
111: {
112: // Case 3A: entry is < 10
113: if (entry < 10)
114: {
115: System.out.printf(" %d ", (int)entry);
116: }
117: // Case 3B: entry is >= 10
118: else
119: {
120: System.out.printf(" %d ", (int)entry);
121: }
122: }
123: }
124: System.out.println("]");
125: }
126: }
128: // Path reconstruction method
129: public static List<Edge> reconstructPath
130: (
131: Graph graph,
132: List<Vertex> vertices,
133: Vertex startVertex,
134: Vertex endVertex,
135: double[][] distMatrix
136: )
137: {
138: int startIndex = vertices.indexOf(startVertex);
139: ArrayList<Edge> path = new ArrayList<Edge>();
141: // Backtrack from the ending vertex
142: int currentIndex = vertices.indexOf(endVertex);
143: while (currentIndex != startIndex)
144: {
145: Collection<Edge> incomingEdges =
146: graph.getEdgesTo(vertices.get(currentIndex));
148: boolean foundNext = false;
149: for (Edge currentEdge : incomingEdges)
150: {
151: double expected =
152: distMatrix[startIndex][currentIndex]
153: - currentEdge.weight;
154: double actual =
155: distMatrix[startIndex]
156: [vertices.indexOf(currentEdge.fromVertex)];
157: if (expected == actual)
158: {
159: // Update current vertex index
160: currentIndex = vertices.indexOf(currentEdge.fromVertex);
162: // Prepend currentEdge to path
163: path.add(0, currentEdge);
165: // The next vertex in the path was found
166: foundNext = true;
168: // The correct incoming edge was found,
169: // so break the inner loop
170: break;
171: }
172: }
174: if (!foundNext)
175: {
176: return null;
177: }
178: }
180: return path;
181: }
183: public static void main(String[] args)
184: {
185: String[] graphVertices =
186: {
187: "A,B,C,D",
188: "A,B,C,D",
189: "A,B,C",
190: "A,B,C,D,E"
191: };
192: String[] graphEdges =
193: {
194: "AB2,BC-3,BD7,CA5,DA-4",
195: "AB4,BC3,CD6,DA-1,DB7",
196: "AB1,AC1,BC-8",
197: "AB1,AE8,BC2,CD3,DA-5,ED9"
198: };
199: String[] graphPaths =
200: {
201: "CD", // Show path from C to D in graph 1
202: "DB", // Show path from D to B in graph 2
203: "CA", // Show path from C to A in graph 3
204: "AD" // Show path from A to D in graph 4
205: };
207: // Build each graph and the all pairs shortest path matrix for each
208: for (int graphNum = 1; graphNum <= graphVertices.length; graphNum++)
209: {
210: // Create a new graph
211: Graph graph = new Graph();
213: // Create and add vertices to the graph and an ArrayList
214: ArrayList<Vertex> vertices = new ArrayList<Vertex>();
215: for (String vertexName : graphVertices[graphNum - 1].split(","))
216: {
217: vertices.add(graph.addVertex(vertexName));
218: }
220: // Parse and add edges
221: String edgesString = graphEdges[graphNum - 1];
222: for (String edgeString : edgesString.split(","))
223: {
224: Vertex fromVertex =
225: graph.getVertex(edgeString.substring(0, 1));
226: Vertex toVertex =
227: graph.getVertex(edgeString.substring(1, 2));
228: double weight = Double.parseDouble(edgeString.substring(2));
229: graph.addDirectedEdge(fromVertex, toVertex, weight);
230: }
232: // Get the all pairs shortest path matrix
233: ArrayList<Edge> allEdges = new ArrayList<Edge>(graph.getEdges());
234: double[][] matrix = allPairsShortestPath(vertices, allEdges);
236: // Display the matrix
237: System.out.printf
238: (
239: "All pairs shortest path matrix (graph %d):%n",
240: graphNum
241: );
242: displayMatrix(matrix, vertices);
244: // Show an actual path sequence
245: String startVertexLabel = graphPaths[graphNum - 1].substring(0, 1);
246: String endVertexLabel = graphPaths[graphNum - 1].substring(1, 2);
247: System.out.printf
248: (
249: "Shortest path from %s to %s:%n",
250: startVertexLabel,
251: endVertexLabel
252: );
253: Vertex startVertex = graph.getVertex(startVertexLabel);
254: Vertex endVertex = graph.getVertex(endVertexLabel);
255: List<Edge> path = reconstructPath
256: (
257: graph,
258: vertices,
259: startVertex,
260: endVertex,
261: matrix
262: );
263: if (path == null || path.size() == 0)
264: {
265: System.out.println("No path");
266: }
267: else
268: {
269: System.out.print(path.get(0).fromVertex.label);
270: for (Edge edge : path)
271: {
272: System.out.print(" to " + edge.toVertex.label);
273: }
274: System.out.println();
275: }
276: System.out.println();
277: }
278: }
279: }