Scribd
Upload
6 views30 pages

11 Dijkstra Algorithm

The document discusses Dijkstra's Algorithm, which is used to solve the Single Source Shortest Path Problem in directed graphs. It outlines the algorithm's key ideas, initialization, and proof of correctness using mathematical induction. Additionally, it addresses potential issues with negative edge weights and cycles, and includes homework assignments related to these topics.

Uploaded by

Soumyadeep Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views30 pages

11 Dijkstra Algorithm

The document discusses Dijkstra's Algorithm, which is used to solve the Single Source Shortest Path Problem in directed graphs. It outlines the algorithm's key ideas, initialization, and proof of correctness using mathematical induction. Additionally, it addresses potential issues with negative edge weights and cycles, and includes homework assignments related to these topics.

Uploaded by

Soumyadeep Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithms and Programming

Dijkstra’a Algorithm
Y. Narahari
Graphs
Directed Graphs
Example of a Digraph
Graphs
Single Source Shortest Path Problem (SSSP)
Dikjstra’s Algorithm for SSSP Problem
Dijkstra’s Algorithm: Key Idea

Initially S = {1}. At any point of time, S includes all those


vertices v to which the shortest path from “1” is known.
The distance array “d”
An Example

Initialization : S = {1}
D[1] = 0; D[2] = 10; D[3] = infty; D[4] = 30; D[5] = 100
The Greedy Strategy
Iteration 1
Iteration 2
Iteration 3
Iteration 4
Proof of Correctness of Dijkstra’s Algorithm
Proof Technique: Mathematical Induction
Any vertex belongs to S or V - S. We show (a) and (b) by induction
Induction: Basis
Induction for Condition (a)
Induction for Condition (a) - continued
Induction for Condition (a) - continued
Induction for Condition (a) - continued

Suppose x is the first non-special vertex that the


“so called” shortest path touches before eventually
reaching v. Then:
Induction for Condition (a) - continued
Induction for (b)

Condition (b) : For vertex “w” belonging to V – S,


D[w] gives the cost of the shortest special path
from “1” to “w”
We know that “v” is the vertex that is just added to S.
When “v” is added to S, there are two possibilities for
the special shortest path from “1” to “w” : either
passes through “v” or does not pass through “v”
Induction for condition (b) - continued
1. Does not pass through “v” in which case there is nothing
to prove because according to induction hypothesis,
D[w] is the cost of the shortest special path just before
“v” was added

2. Passes through “v” in which case it may possibly pass


through other nodes of S before reaching “w”. Suppose
“y” is the last node in S that this shortest special path to
“w” visits before going from “y” to “w”.
Induction for condition (b) - continued
Induction for condition (b) - continued
What if the edge weights are negative?

Can you think of way of making the Dijkstra’s


algorithm work with negative weights as well?
What if there are cycles?

Homework
Work out some examples to show that cycles
do not affect the working of the algorithm.

Show in general that Dijkstra’s algorithm will


work even if cycles are present.
Computational Complexity

Data structure to be used


“Heap” can be used for implementing V – S
since “deletemin” operation is involved
Homework
If the heap data structure is used for V – S,
what will be the computational complexity of
Dijkstra’s algorithm?

You might also like