Scribd
Upload
186 views4 pages

Dijkstra Algorithm Explained

Dijkstra's algorithm finds the shortest paths between nodes in a graph. It works by starting at the initial node and searching outward, marking distances to neighboring unvisited nodes. It iteratively visits the unvisited node with the lowest distance and updates distances if a shorter path is found, until all nodes are visited. The time complexity is O(V^2) for a graph with V vertices as each node is processed once and its neighbors checked. The algorithm returns the shortest path by tracking predecessor nodes.

Uploaded by

Satya Raghav
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
186 views4 pages

Dijkstra Algorithm Explained

Dijkstra's algorithm finds the shortest paths between nodes in a graph. It works by starting at the initial node and searching outward, marking distances to neighboring unvisited nodes. It iteratively visits the unvisited node with the lowest distance and updates distances if a shorter path is found, until all nodes are visited. The time complexity is O(V^2) for a graph with V vertices as each node is processed once and its neighbors checked. The algorithm returns the shortest path by tracking predecessor nodes.

Uploaded by

Satya Raghav
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
You are on page 1/ 4

1

Graph Theory in Computer Science


Graphs find their importance as models for many kinds of processes and structures in
subjects as diverse as electrical engineering, chemistry, transportation system, geography,
sociology.
In Computer Science we study the methods to represent Graphs with the data structures
available to us. We are also interested in the design of Algorithms for processing Graphs.
We will focus on the analysis of one of the most interesting graph algorithm which is
called Dijkstra Algorithm.

Dijkstra Algorithm
Dijkstra Algorithm is named for Computer Scientist Edsgar Dijkstra, who proposed the
algorithms for finding the shortest path between two vertices. We start with the problem
of finding a shortest path from one vertex to another. Well concentrate simply on
finding the weight of the shortest path-in other words the smallest possible sum of
weights along a path from one vertex to another.
We will illustrate how the algorithm works with the following small graph:

V0
2
9
6

V5

V1
15
8

3
V3
6
1

V2

V4

The algorithm begins by filling in one value in the distance array. We fill with zero the
cell associated with the start vertex (there is an empty path from start vertex to itself).The
other values in the array are unknown and will be represented by infinity symbol .
This is the first version of the distance array
0
[0]

[1]

[2]

[3]

[4]

[5]

These are the crucial steps of the algorithm:


1. We initialize a set G called allowed vertices to be an empty set
2. Throughout the algorithm a permitted path is a path that has the following
properties:
it starts at the start vertex
each vertex on the path(except perhaps, the final vertex) belongs to the set
of allowed vertices G
the final vertex in the allowed path does not need to be in G
3. We first add V0 to G and update the distance array. Then we add the next
unallowed vertices to G and, again updated the distance array. The procedure
terminate when all vertices are allowed.
4. How do we chose the next unallowed vertex to add to G? We always have to
choose the unallowed vertex that has the smallest current value in the distance
array

0
[0]

0
[0]

[1]

[1]

G={ V0 , V1}

[2]

10
[2]

[3]

17
[3]

[4]

[4]

[5]

8
[5]

[0]

[1]

10
[2]

17

11

[3]

[4]

[5]

G={ V0 , V1 , V5}

[0]

[1]

10
[2]

11

11

[3]

[4]

[5]

G={ V0 , V1 , V2, V5}

[0]

[1]

10
[2]

11

11

[3]

[4]

[5]

G={ V0 , V1 , V2, V5, V4}

[0]

[1]

10
[2]

11

11

[3]

[4]

8
[5]

G={ V0 , V1 , V2, V5, V4, V3}


To restore the shortest path chain we would need a predecessor information. For each
vertex we will record a predecessor at every stage of construction of the distance array.
distance

vertices

V0

V1

V2

V3

V4

V5

predecessors

V0

V0

distance

10

17

vertices

V0

V1

V2

V3

V4

V5

V0

V1

V1

predecessors

V1

distance

10

17

11

vertices

V0

V1

V2

V3

V4

V5

V0

V1

V1

V5

V1

predecessors

distance

10

11

11

vertices

V0

V1

V2

V3

V4

V5

V0

V1

V2

V5

V1

predecessors

Adding V0 and V1 does not change the distance array, and therefore, a predecessor array.
distance

10

11

11

vertices

V0

V1

V2

V3

V4

V5

V0

V1

V2

V5

V1

predecessors

Now we can restore the shortest path from V0 to V3 .

V0 V1 V2 V3 .

Indeed, if we add the weights that labeled the arrows and sum it up, we can see the result
coincides with the data in the distance array.

V0 V1 V2 V3
2

Now we are ready to write a code an to provide Complexity Analysis for Dijkstra
Algorithm.

You might also like