Dijkstras Shortest Path

Related data structure:

• ADT - Graph

---

Dijkstra’s algorithm is the algorithm to find the shortest path in a weighted graph with non-negative weight edge, it is suitable for single source (one vertex is chosen to be the start) path problems for either directed or undirected paths. If a graph contains negative weight, the Bellman-Ford algorithm can be used instead. Dijkstra’s algorithm takes a source vertex, mark vertices as visited in each iteration, and it needs an overview of the current shortest distance to each vertex as it works its ways through the graph, updating these distances when a shorter distance is found.

Implementation

1. Assign a tentative distance value (infinite) to every node, set the starting node distance value to 0.
2. Set the initial node as current node.
3. Create a set of all unvisited nodes called the unvisited set.
4. For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
5. After considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will not be checked again.
6. If the destination node has been marked visited or if the smallest tentative distance among the nodes in the unvisited set is infinity (there is no connection between the initial node and remaining unvisited nodes), then stop.
7. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new current node, go back to step 3.

This implementation uses adjacency list to implement the graph.

public class Dijkstra {
	public static class GraphAjdList {
		private int vertices;
		private LinkedList<Edge>[] adjList;
		
		class Edge {
			int target;
			int weight;
			Edge(int target, int weight) {
				this.target = target;
				this.weight = weight;
			}
		}
		
		class Node implements Comparator<Node> {
			int node;
			int cost;
			Node(int node, int cost) {...}
			
			@Override
			public int compare(Node node1, Node node2) {
				if (node1.cost < node2.cost) {
					return -1;
				}
				if (node1.cost > node2.cost) {
					return 1;
				}
				return 0;
			}
		}
		
		// graph constructor
		Graph(int vertices){...} 
		void addEdge(int source, int target, int weight) {
			adjList[source].add(new Edge(target, weight));
		}
		
		// param: start node
		void dijstraAlgo(int start) {
			// param: number of vertices and a node comparator
			PriorityQueue<Node> pq = new PriorityQueue<>(vertices, new Node());
			int[] distance = new int[vertices];
			// keeps track of whether the shortest path to each node
			// has been finalised
			boolean[] shortestPathTree = new boolean[vertices];
			
			Arrays.fill(distance, Integer.MAX_VALUE);
			distance[start] = 0; // set the starting node distance to 0
			pq.add(new Node(start, 0));
			
			while (!pq.isEmpty()) {
				int u = pq.remove().node;
				if (shortestPathTree[u]) continue;
				shortestPathTree[u] = true;
			}
			for (Edge edge : adjList[u]) {
				int v = edge.target;
				int weight = edge.weight;
			}
			if (!shortestPathTree[v]&&distance[u]+weight<distances[v]) {
				distances[v] = distances[u] + weight;
				pq.add(new Node(v, distances[v]));
			}
		}
	}
}