Scribd
Upload
83 views2 pages

Dijk Stra Shortest Path Example

The document illustrates Dijkstra's algorithm for finding the shortest path from vertex v1 to other vertices in a graph. It details the process of updating costs for neighboring vertices and selecting the vertex with the lowest cost iteratively. The final graph shows the costs associated with each vertex and includes exercises for further practice.

Uploaded by

Surya Anusha
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
83 views2 pages

Dijk Stra Shortest Path Example

The document illustrates Dijkstra's algorithm for finding the shortest path from vertex v1 to other vertices in a graph. It details the process of updating costs for neighboring vertices and selecting the vertex with the lowest cost iteratively. The final graph shows the costs associated with each vertex and includes exercises for further practice.

Uploaded by

Surya Anusha
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/ 2

Dijkstra’s Shortest Path Example

Example 1: Vertex v1

0 0
∞ Cost of v1 is 0. 4
V1 4
V2 V1 4
V2
S  v1

2 There is a path to all


8 8 2
1 neighbors. Each will 1
2 be updated. 2
V3 V4 V1 is marked. V3
3
V4
3
∞ ∞ 2
8

0 43
Pick vertex not in S with lowest cost (v4) and
4
update neighbors. V1 V2

Only path is to v2.


8 2
Min (4,2+1) = 3 – Change v2 cost 1
2

V3 V4
3
8 2

0 43
Again, pick vertex not in S with lowest cost (v2) 4
V1 V2
and update neighbors.

Only path is to v3. 2


8
1
Min (8,3+2) = 5 – Change v3 cost
2

Path v0 to v3: (v1, v4, v2, v3) V3 V4


3
85 2
Dijkstra’s Shortest Path Example
Again, pick vertex not in S with lowest cost
and update neighbors. v3 is only choice 0 43
4
V3 has a path only to v4. Cost to v4 from v0 V1 V2
is Min(2,5+3). Do not update v4 cost.

8 2
1
2

V3 V4
3
85 2
0 43
Final graph, with costs
4
V1 V2

8 2
1
Exercises: Repeat for vertices v2, v3, and v4. 2

1. Note that v1 is not accessible from V3 V4


other vertices. 3

2. Find the transitive closure of this 85 2


graph.

You might also like