Question

2. Find the minimum weight paths from the black vertex to all the other vertices in the graph below using Dijkstra's algorithm. Show the value of the distance vector after each step. 8 14 20 25 2 18 11 16 10 16 6 17

Answer 1

Answer 2:

Dijkstra's algorithm:-

1. Let the distance of all vertices from vertex K is infinity and distance of K from K is 0.

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	0

2. Relax all edges connected to vertex K:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	$\infty$	$\infty$	16	$\infty$	$\infty$	$\infty$	$\infty$	11	10	6	0

K is now marked as visited.

3. Relax all edges connected to vertex J:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	$\infty$	$\infty$	16	$\infty$	$\infty$	$\infty$	$\infty$	11	10	6	0

J is now marked as visited.

4. Relax all edges connected to vertex I:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	$\infty$	24	16	$\infty$	$\infty$	$\infty$	$\infty$	11	10	6	0

I is now marked as visited.

5. Relax all edges connected to vertex H:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	$\infty$	24	16	$\infty$	$\infty$	$\infty$	15	11	10	6	0

H is now marked as visited.

6. Relax all edges connected to vertex C:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	32	23	$\infty$	15	11	10	6	0

C is now marked as visited.

7. Relax all edges connected to vertex G:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	32	20	$\infty$	15	11	10	6	0

G is now marked as visited.

8. Relax all edges connected to vertex A:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	27	20	$\infty$	15	11	10	6	0

A is now marked as visited.

9. Relax all edges connected to vertex E:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	27	20	37	15	11	10	6	0

E is now marked as visited.

10. Relax all edges connected to vertex B:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	27	20	37	15	11	10	6	0

B is now marked as visited.

11. Relax all edges connected to vertex D:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	27	20	37	15	11	10	6	0

D is now marked as visited.

12. Relax all edges connected to vertex F:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	27	20	37	15	11	10	6	0

F is now marked as visited.

All nodes are visited completely.

Shortest path distance from vertex K to all other vertices:-

Vertex	A	B	C	D	E	F	G	H	I	J	K
Distance from K	18	24	16	27	20	37	15	11	10	6	0

the lowest distance is 18 the lowest distance is 24 B the lowest distance is 11 14 18 20 25 he lowest distance is 10 the lowest distance is 27 D 16 the lowest distance is 16 the lowest distance is 15 the lowest distance is 6 10 the lowest distance is 37 16 5 17 west distance ie 20 6 the lowest distance is 0. K G