Dijkstra’s algorithm is an algorithm to find the shortest paths from the 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 the least weight. When you go further down the road, and find other routes with less weight, you replace the total weight accordingly.

dijkstra's algorithm

In this implementation, the weighted graph is represented as an adjacency list. You can use the 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 a smaller distance is picked first.

In Java, you use the PriorityQueue class provided by Java collections. In Python, use heapq from the library. In JavaScript, there is no open-box priority queue. You can implement your 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