Page 219 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Best example of D-Heap is “DJIKSTRA’S ALGORITHM”

Djikstra’s algorithm (named after its discover, Dutch computer scientist E.W. Dijkstra) solves the
problem of finding the shortest path from a point in a graph (the source) to a destination with

non-negative weight edge.

It turns out that one can find the shortest paths from a given source to all vertices (points) in
a graph in the same time. Hence, this problem is sometimes called the single-source shortest

paths problem. Dijkstra’s algorithm is a greedy algorithm, which finds shortest path between all
pairs of vertices in the graph. Before describing the algorithms formally, let us study the method
through an example.
Figure 10.6: A Directed Graph with no negative edge(s)

1 3 2

6 9 1
8
3 4
6 6
5

Dijkstra’s algorithm keeps two sets of vertices:
S is the set of vertices whose shortest paths from the source have already been determined
Q = V-S is the set of remaining vertices.
The other data structures needed are:
d array of best estimates of shortest path to each vertex from the source pi an array of predecessors
for each vertex. predecessor is an array of vertices to which shortest path has already been
determined.

The basic operation of Dijkstra’s algorithm is edge relaxation. If there is an edge from u to v, then
the shortest known path from s to u can be extended to a path from s to v by adding edge (u,v)
at the end. This path will have length d[u]+w(u,v). If this is less than d[v], we can replace the
current value of d[v] with the new value.
The predecessor list is an array of indices, one for each vertex of a graph. Each vertex entry
contains the index of its predecessor in a path through the graph.

Operation of Algorithm

The following sequence of diagrams illustrate the operation of Dijkstra’s Algorithm. The bold
vertices indicate the vertex to which shortest path has been determined.

Initialize the graph, all the vertices have infi nite costs
except the source vertex which has zero cost

214 LOVELY PROFESSIONAL UNIVERSITY