-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathDijkstraWithPathOutput.java
More file actions
148 lines (120 loc) · 5.75 KB
/
DijkstraWithPathOutput.java
File metadata and controls
148 lines (120 loc) · 5.75 KB
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/**
* Author: Kevin Richardson <[email protected]>
* Date: 10/26/11
* Time: 7:21 PM
*
* An implementation of the single source shortest path (Dijkstra's) algorithm
* modified to use a "comeFrom" value to print the nodes comprising shortest paths.
*/
import java.util.Scanner;
public class DijkstraWithPathOutput {
static MatrixGraph graph;
static int[] previousConnections;
static Scanner keyboardScanner;
public static void main(String[] args)
{
// Scan the requested graph into its storage structure.
keyboardScanner = new Scanner(System.in);
System.out.print("Enter desired graph input file: ");
graph = new MatrixGraph(keyboardScanner.nextLine());
// Run Dijkstra's algorithm on this graph starting at node 0.
singleSourceShortestPath(graph, 0);
}
public static void singleSourceShortestPath(MatrixGraph graph, int startNode)
{
// Get the table of node previousConnections.
int[][] table = graph.table;
// Get the list of which nodes have been visited.
boolean[] visited = graph.visited;
// Maintain a list of "comeFrom" values -- the node with shortest path connection from startNode to node
// previousConnections[node].
previousConnections = new int[table.length];
// Store the best distance between the startNode and each other node.
// An unknown distance (infinity) is represented as Integer.MAX_VALUE.
int[] distances = new int[table.length];
// Prefill our distances table with known values.
// Also fill the previousConnections out to start with no comeFroms.
for(int i = 0; i < distances.length; i++)
{
previousConnections[i] = -1;
if(i == startNode)
{
distances[i] = 0;
previousConnections[i] = startNode;
}
// Fill in the known values in our distances table (direct previousConnections in the graph itself).
// Because the previousConnections are stored as infinity in the table, we can pull direct values.
// We can also have the startNode as the comeFrom for these values since a direct connection exists.
else
{
distances[i] = table[startNode][i];
previousConnections[i] = startNode;
}
}
// Mark the start known as visited.
visited[startNode] = true;
// Set the node to use as a reference point to calculate the distance to all the other nodes from startNode.
for(int referenceNode = 0; referenceNode < table.length; referenceNode++)
{
// No reason to check the startNode as we've already prefilled its distances.
if(referenceNode != startNode)
{
// Based off this reference node, calculate the distance from the startNode to all other nodes in the
// graph.
for(int i = 0; i < table.length; i++)
{
// We don't need to examine from already-visited nodes because of greedy approach.
if(!visited[i])
{
// Contains the newDistance between the startNode and this node by going through
// referenceNode. Assumes the route is unreachable by default.
int newDistance = Integer.MAX_VALUE;
// If a route is possible, calculate the new distance between startNode and this node when
// going through the reference node.
if(table[referenceNode][i] < Integer.MAX_VALUE)
{
newDistance = distances[referenceNode] + table[referenceNode][i];
}
// If this new distance is smaller than the previous, add it to the table of shortest paths
// to node i from startNode. Mark the reference node as the comeFrom.
if(newDistance < distances[i])
{
distances[i] = newDistance;
previousConnections[i] = referenceNode;
}
}
}
// Mark the reference node as visited.
visited[referenceNode] = true;
}
}
// Print out the list of distances from startNode to each other node.
System.out.println("Shortest path from " + startNode + " to...");
for(int i = 0; i < distances.length; i++)
{
// Print out the distance from startNode to i.
String distance = distances[i] == Integer.MAX_VALUE ? "unreachable" : Integer.toString(distances[i]);
System.out.println(i + ": " + distance);
// Print the path from startNode to i by building the path backwards.
String path = "";
int currentNode = i;
int comeFrom = previousConnections[currentNode];
while(comeFrom != -1)
{
path += currentNode + " ";
if(currentNode != startNode)
{
path += ">-- ";
}
if(currentNode == startNode)
{
break;
}
currentNode = comeFrom;
comeFrom = previousConnections[currentNode];
}
// Print out the path in the correct direction.
System.out.println("\tPath: " + new StringBuffer(path).reverse().toString());
}
}
}