Dijkstra’s algorithm is an algorithm to find the shortest paths from source node to other nodes in a weighted graph, both directed and undirected. It is a greedy algorithm. Starting from the source node, you always choose an edge with least weight. When you go further down the road, and find other route with less weight, you replace the total weight accordingly.

dijkstra's algorithm

In this implementation, the weighted graph is represented as a adjacency list. You can use existing class of WeightedGraph. A priority queue is used to sort edges by their weights. The smaller one is at the front, so that edge with smaller distance is picked first.

In Java, you use PriorityQueue class provided by Java collections. In Python, use heapq from library. In JavaScript, there is no open-box priority queue. You can implement you own PriorityQueue class.

Table of Content


Dijkstra’s algorithm

Java

Javascript

Python


Free download

Download Dijkstra in Java, JavaScript and Python
Shortest path and 2nd shortest path using Dijkstra