Dijkstra’s algorithm solves the single source shortest path problem on a weighted, directed graph only when all edge-weights are non-negative. It maintains a set S of vertices whose final shortest path from the source has already been determined and it repeatedly selects the left vertices with the minimum shortest-path estimate, inserts them into S, and relaxes all edges leaving that edge. In this we maintain a priority-Queue which is implemented via heap.
Input Format: Graph is directed and weighted. First two integers must be number of vertices and edges which must be followed by pairs of vertices which has an edge between them.
Related Tutorials (basic Graph Algorithms) :
Some Important Data Structures and Algorithms, at a glance:
Basic Data Structures and Algorithms
Sorting- at a glance
Computer Science >