class PathVertexInfo
public class BellmanFordDemo
1: //BellmanFordDemo.java
3: import java.util.HashMap;
5: // Stores vertex information that is relevant to a shortest path algorithm
6: class PathVertexInfo
7: {
8: public Vertex vertex;
9: public double distance;
10: public Vertex predecessor;
12: public PathVertexInfo(Vertex vertex)
13: {
14: this.vertex = vertex;
15: distance = Double.POSITIVE_INFINITY;
16: predecessor = null;
17: }
18: }
20: public class BellmanFordDemo
21: {
22: public static HashMap<Vertex, PathVertexInfo> bellmanFord
23: (
24: Graph graph,
25: Vertex startVertex
26: )
27: {
28: // Initialize a PathVertexInfo object for each vertex.
29: // Each PathVertexInfo object has an infinite distance
30: // and null predecessor by default.
31: HashMap<Vertex, PathVertexInfo> info;
32: info = new HashMap<Vertex, PathVertexInfo>();
33: for (Vertex currentVertex : graph.getVertices())
34: {
35: PathVertexInfo currentVertexInfo =
36: new PathVertexInfo(currentVertex);
37: info.put(currentVertex, currentVertexInfo);
38: }
40: // startVertex has a distance of 0 from itself
41: info.get(startVertex).distance = 0.0;
43: // Main loop is executed |V|-1 times to guarantee minimum distances
44: for (int i = 0; i < info.size() - 1; i++)
45: {
46: // The main loop
47: for (Vertex currentVertex : graph.getVertices())
48: {
49: for (Edge edge : graph.getEdgesFrom(currentVertex))
50: {
51: Vertex adjacentVertex = edge.toVertex;
52: double alternativePathDistance =
53: info.get(currentVertex).distance + edge.weight;
55: // If a shorter path from startVertex to adjacentVertex
56: // has been found, update adjacentVertex's distance and
57: // predecessor
58: PathVertexInfo adjacentInfo = info.get(adjacentVertex);
59: if (alternativePathDistance < adjacentInfo.distance)
60: {
61: adjacentInfo.distance = alternativePathDistance;
62: adjacentInfo.predecessor = currentVertex;
63: }
64: }
65: }
66: }
68: // Check for a negative edge weight cycle
69: for (Vertex currentVertex : graph.getVertices())
70: {
71: for (Edge edge : graph.getEdgesFrom(currentVertex))
72: {
73: Vertex adjacentVertex = edge.toVertex;
74: double alternativePathDistance =
75: info.get(currentVertex).distance + edge.weight;
77: // If a shorter path from startVertex to adjacentVertex is still
78: // found then a negative edge weight cycle exists
79: if (alternativePathDistance < info.get(adjacentVertex).distance)
80: {
81: return null;
82: }
83: }
84: }
86: return info;
87: }
89: public static String getShortestPath
90: (
91: Vertex startVertex,
92: Vertex endVertex,
93: HashMap<Vertex, PathVertexInfo> infoMap
94: )
95: {
96: // Start from endVertex and build the path in reverse.
97: String path = "";
98: Vertex currentVertex = endVertex;
99: while (currentVertex != startVertex)
100: {
101: path = " -> " + currentVertex.label + path;
102: currentVertex = infoMap.get(currentVertex).predecessor;
103: }
104: path = startVertex.label + path;
105: return path;
106: }
108: public static void main(String[] args)
109: {
110: Graph graph = new Graph();
111: Vertex vertexA = graph.addVertex("A");
112: Vertex vertexB = graph.addVertex("B");
113: Vertex vertexC = graph.addVertex("C");
114: Vertex vertexD = graph.addVertex("D");
115: Vertex vertexE = graph.addVertex("E");
116: Vertex vertexF = graph.addVertex("F");
117: Vertex[] vertices =
118: {
119: vertexA,
120: vertexB,
121: vertexC,
122: vertexD,
123: vertexE,
124: vertexF
125: };
126: graph.addDirectedEdge(vertexA, vertexB, 1);
127: graph.addDirectedEdge(vertexA, vertexC, 2);
128: graph.addUndirectedEdge(vertexB, vertexC, 1);
129: graph.addUndirectedEdge(vertexB, vertexD, 3);
130: graph.addDirectedEdge(vertexB, vertexE, 2);
131: graph.addUndirectedEdge(vertexC, vertexE, 2);
132: graph.addDirectedEdge(vertexD, vertexC, 1);
133: graph.addUndirectedEdge(vertexD, vertexE, 4);
134: graph.addDirectedEdge(vertexD, vertexF, 3);
135: graph.addDirectedEdge(vertexE, vertexF, 3);
137: // Set starting vertex for shortest paths
138: Vertex startVertex = vertexA;
140: // Run Bellman-Ford's shortest path algorithm. Display results if
141: // successful, or error message if a negative edge weight cycle exists.
142: HashMap<Vertex, PathVertexInfo> result =
143: bellmanFord(graph, startVertex);
144: if (result != null)
145: {
146: for (Vertex vertex : vertices)
147: {
148: String path = getShortestPath(startVertex, vertex, result);
149: System.out.printf
150: (
151: "%s -> %s: %s (%d)%n",
152: startVertex.label,
153: vertex.label,
154: path,
155: (int)result.get(vertex).distance
156: );
157: }
158: }
159: else
160: {
161: System.out.println
162: (
163: "Bellman-Ford failed, negative edge weight cycle detected."
164: );
165: }
166: }
167: }