In unweighted shortest path, all the edges are assigned to 1.

__DIJKSTRA’S
ALGORITHM:__

__Unweighted shortest Path__

In
unweighted shortest path, all the edges are assigned to 1.

**Required Information**

**i.
****known – **Specifies
whether the vertex is processed or not. It is set to 1 after it is** **processed, otherwise 0. Initially all
vertices are unknown, so all entries marked as 0.

**ii.
****dv – **it
specifies distance form source to vertex. Initially all vertices are
unreachable** **except for S whose path
length is zero.

**iii.
****pv – **It is
book keeping variable, which allow us to print te actual path. i.e., the vertex** **which makes the changes in dv.

**Procedure to find the unweighted shortest path**

i.
Assign the source node as S and Enqueue S.

ii.
Dequeue the vertex S from queue and assign the
value of that vertex to be known and then find its adjacency vertices.

iii.
If the distance of the adjacent vertices is equal
to infinity then change the distance of that vertex as the distance of its
source vertex. Increment by 1 and enqueue the vertex.

iv.
Repeat step ii until the queue becomes empty.

**Routine for unweighted shortest path**

void
unweighted( Table T )

{

Queue Q;
Vertex v, w;

Q =
CreateQueue( NumVertex );

MakeEmpty(
Q );

Enqueue(
S, Q ); while( !IsEmpty( Q ) )

{

v =
Dequeue( Q );

T[v].known
= True;

for each
w adjacent to v

if(
T[w].Dist = = INFINITY )

{

T[w].Dist
= T[v].Dist + 1;

T[w].path
= v;

Enqueue(
w, Q );

}}

DisposeQueue(
Q ); /* free the memory */

}

**Example**

i.
v3 is taken as source node and its path length is
initialized to 0. v3 is inserted into Q.

ii.
v3 find its adjacent node whose path length is 1.
v1, v6 are adjacent nodes to v3 and inserted in to queue.

iii. Find the adjacent node for v1. v2 and v4 are adjacent node for v1, v2 and v4 inserted into the queue.

iv.
No adjacent vertices for v6. No change in path
value for all vertices.

v. Find the adjacent vertices for v2. v4 and v5 are adjacent nodes to v2 and inserted into queue.

vi.
Find the adjacent vertices for v4. v5, v6 and v7
are adjacent vertices. Minimum path length for v7 is 3. v7 is inserted into
queue.

vii. An adjacent vertex for v5 is v7. Already found the minimum path length from v3 to v7 is 3. So no change in dv and pv.

viii.
An adjacent vertex for v7 is v6. Already found the
minimum path length from v3 to v6 is 1. So no change in dv and pv.

**Algorithm Analysis**

Running
time is O(|E| + |V|)

__Weighted Graph__

The
general method to solve the single source shortest path problem is known as

Dijkstra‟s
algorithm. It applied to weighted graph.

**Procedure**

^{Ø }It uses
greedy technique.^{}

^{ }

^{Ø }It
proceeds in stages.^{}

^{ }

^{Ø }It
selects a vertex v, which has the smallest d_{v} among all the unknown
vertices and declares the shortest path from s to v is known.^{}

^{ }

^{Ø }The remainder
consists of updating the value of d_{w}.^{}

^{ }

^{Ø }We
should d_{w} = d_{v} + C_{v,
w}, if the new value for d_{w} would an improvement.^{}

**Example: Find the shortest path for the following
graph.**

1. v_{1} is taken as source.

2. Now v1 is
known vertex, marked as 1. Its adjacent vertices are v_{2}, v_{4},
p_{v} and d_{v} values are
updated

T[v_{2}].
dist = Min (T[v_{2}].dist, T[v_{1}].dist + Cv_{1}, v_{2})
= Min (α , 0+2) = 2

T[v_{4}]. dist = Min (T[v_{4}].dist, T[v_{1}].dist
+ Cv_{1}, v_{4}) = Min (α , 0+1) = 1

3. Select the vertex with minimum distance away v_{2} and v_{4}
. v_{4} is marked as known vertex. Its adjacent vertices are v_{3},
v_{5}, v_{6} and v_{7} .

T[v_{3}].
dist = Min (T[v_{3}].dist, T[v_{4}].dist + Cv_{4}, v_{3})
= Min (α , 1+2) = 3

T[v_{5}].
dist = Min (T[v_{5}].dist, T[v_{4}].dist + Cv_{4}, v_{5})
= Min (α , 1+2) = 3

T[v_{6}].
dist = Min (T[v_{6}].dist, T[v_{4}].dist + Cv_{4}, v_{6})
= Min (α , 1+8) = 9

T[v_{7}].
dist = Min (T[v_{7}].dist, T[v_{4}].dist + Cv_{4}, v_{7})
= Min (α , 1+4) = 5

4. Select
the vertex which is shortest distance from source v_{1}. v_{2}
is smallest one. v_{2} is marked as known vertex. Its adjacent vertices
are v_{4} ad v_{5}. The distance from v_{1} to v_{4 }and v_{5}
through v_{2} is more comparing with previous value of d_{v}.
No change in d_{v} and p_{v} value.

5. Select
tht smallest vertex from source. v_{3} and v_{5} are smallest
one. Adjacent vertices for v_{3} is v_{1} and v_{6}. v_{1}
is source there is no change in dv and pv

T[v_{6}].
dist = Min (T[v_{6}].dist, T[v_{3}].dist + Cv_{3}, v_{6})
= Min (9 , 3+5) = 8

d_{v}
and p_{v} values are updated. Adjacent vertices for v_{5} is v_{7}.
No change in d_{v} and p_{v} value.

6. Next smallest vertex v_{7}. Its adjacent
vertex is v_{6}. T[v_{6}]. dist = Min (T[v_{6}].dist, T[v_{7}].dist
+ Cv_{7}, v_{6}) = Min (8 , 5+1) = 6

d_{v}
and p_{v} values are updated.

7. The
last vertex v_{6} is declared as known. No adjacent vertices for v_{6}.
No updation in the table.

The shortest distance from source v_{1} to
all vertices. v_{1} -> v_{2} = 2

v_{1}
-> v_{3} = 3 v_{1} -> v_{4} = 1 v_{1}
-> v_{5} = 3 v_{1} -> v_{6} = 6 v_{1}
-> v_{7} = 5

**Algorithm Analysis**

Time
complexity of this algorithm

O(|E| +
|V|^{2} ) = O(|V|^{2} )

**Declarations for Dijkstra’s algorithm**

typedef
int Vertex; struct TableEntry

{

List header; /* Adjacency
List*/

int
known;

DistType
Dist;

Vertex
Path

};

/*
Vertices are numbered from 0*/ #define NotAVertex (-1)

typedef
struct TableEntry Table[NumVertex];

**Table Initialization routine**

void
InitTable(Vertex Start, Graph G, Table T)

{

int i;
ReadGraph(G,T);

for (i=0;
i<NumVertex; i++)

{

T[i].known
= False;

T[i].
Dist = Infinity;

T[i].
Path = NotAVertex;

}

T[Start].
Dist = 0;

}

**Routine to print the actual shortest path**

void
Printpath(Vertex V, Table T)

{

if(T[V].
Path != NotAVertex)

{

PrintPath(T[V].
Path, T); printf(“to”);

}

printf(“%v”,
V);

/* %v is
pseudocode*/

}

**Pseudocode for Dijkstra’s algorithm**

void
Dijkstra(Table T)

{

Vertex v,
w; for( ; ;)

{

v =
smallest unknown distance vertex;

if( v = =
NotAVertex)

break;

T[v]. kown = True;

for each w adjacent to v if(!T[w].known)

if(T[v].Dist
+ C_{vw} < T[w]. Dist)

{

/* update
w*/

Decrease(T[w].
Dist to T[v].Dist + C_{vw);}

T[w].
path = v;

}

}

}

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Graphs : Dijkstra’s Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.