Implement Dijkstra’s Algorithm (Shortest Path) in Java using Priority Queue

Algorithm Name

Dijkstra Algorithm

Programming Language

Java

Category

Graph Algorithms

Difficulty Level

Medium (Intermediate)

Algorithm Description

Problem Statement

Implement Dijkstra’s Algorithm to find the shortest path from a single source vertex to all other vertices in a weighted graph (non-negative edge weights) using a priority queue (min-heap) for optimization.

Requirements

Programming Language: Java

Folder: algorithms/graph_algorithms

Input:

Number of vertices: V

Number of edges :E

Edges with weights (u, v, w)

Starting vertex :s

Tasks

Implement Dijkstra’s Algorithm using priority queue (min-heap) to select the next vertex efficiently.

Represent the graph using an adjacency list.

Include time complexity (O((V+E) log V)) and space complexity in comments.

Add clear inline comments explaining each step of the algorithm.

Include sample test cases for:

Small connected graph

Graph with multiple paths

Single-node graph

Additional Notes

Negative edge weights are not supported (Dijkstra assumes non-negative edges).

Follow the repo’s folder and naming conventions.

Ensure code compiles successfully and passes any CI tests.

References (Optional)

https://www.geeksforgeeks.org/problems/implementing-dijkstra-set-1-adjacency-matrix/1

Contribution Intent

• I would like to implement this algorithm myself
• I'm requesting this for someone else to implement
• I need help implementing this algorithm

Code of Conduct

• I agree to follow this project's Code of Conduct