Introduction

Dijkstra’s Algorithm is a single-source shortest-path algorithm – i.e., it calculates shortest path and shortest-path weight from a given vertex to all other vertices in the graph.

A greedy algorithm is an algorithm where we keep looking for next best local solutions – and turns out it gives the global solution eventually.

For example, imagine the pre-independence struggle era. British made use of the local issues – like religious differences, hatred between different states in India etc. to divide and rule the country. (That’s another programming paradigm, called divide and conquer) To solve this problem and to unify everyone in the fight against British, the leaders of independence struggle solved the issues between local states, which contributed to the bigger problem of unified fight against British.

Greedy algorithms need not always work, but in some cases, they seem to work perfectly, like Prim’s, Krushkal’s and Dijkstra’s.

Note that Dijkstra’s algorithm, like all other graph algorithms before it in CLRS, makes use of adjacency list datatype.

Problem Statement

• Input | A directed graph G = (V, E), it’s non-negative weight function w (all edges have non-negative weights) and start vertex ‘s’.
• Output | Shortest-path and shortest-path weight of each vertex from the vertex ‘s’ (saved in the attribute ‘d’ of each vertex.)

Pages: <<Contents 2 Next Page >>