Shortest Path

Given a graph with weighted edges (where the weight is the distance between the adjacent nodes) and unweighted nodes this will determine the shortest path between a source node and a target node.

// Dijkstra's Shortest Path Algorithm
public void shortestPath(int source, int target) {
// The distance cost for each node.
int[] dist = new int[nodeCount];
// The array to keep track of visited nodes.
boolean[] visited = new boolean[nodeCount];
// Clear all parents and distances
for (int i = 0; i < nodeCount; i++) {
dist[i] = Integer.MAX_VALUE;
parent[i] = -1;
}
// No cost for the source node.
dist[source] = 0;
// Test all nodes until target is found.
for (int i = 0; i < nodeCount; i++) {
// Find the index of the shortest unvisited edge
int minIndex = -1;
for (int j = 0; j < nodeCount; j++) {
if (!visited[j] && (minIndex == -1 || (dist[j] < dist[minIndex])))
minIndex = j;
}
// If the minimum is infinity then exit
if (dist[minIndex] == Integer.MAX_VALUE)
break;
// This node has been visited.
visited[minIndex] = true;
// Traverse all neighboring nodes connected to minIndex.
for (int j = 0; j < nodeCount; j++) {
// The edge must exist...
if (edge[minIndex][j] != 0) {
// Calculate the travel distance if we go to this edge.
int newDistance = dist[minIndex] + edge[minIndex][j];
// If the new distance is less then track the movement.
if (newDistance < dist[j]) {
dist[j] = newDistance;
parent[j] = minIndex;
}