How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)

How To Get Min-Cost Between twopoints in graph

(Dijkstra’s algorithm)

Now See This Graph :

which is just like asubway map .

Now Question is :

how to calculate fromA to (B,C,D,E,F,G,H,I,J) min cost ?

Now Let's go through Dijkstra's algorithm.

I will start follow these steps :

Step 1:

Take point from (A,B,C,D,E,F,G,H,I,J) .

Step 2:

find out the points it can reach ,save as reached-points

Step 3:

update the reached-points distance by the new dist if it is smaller than the old value

ok , now take A, and we can see ,A can reach B,C,D

Now I take B. B Can Reach D,E. SoI need to update the value for D,E

As 4+3 < 8 . sothe value for D updated to 7.

Next ,Take C. C canreach D,F ,So I Need to update D,F values

Next ,Take D , D CanReach B,C,E,F,G , I Need to update them relatively .

But Can See ,D'svalue is 6 ,gather than B(4) and C(5) ,so no need update for B,C.

Next, Take E. whichCan Reach B,D,G,H

E(15)>B(4) ,E(15) > D(6), no updating.

E(15) + 6 >G(16),So no updating for G(16).

Next ,F .Can reach C,D,G,I

For C,D .

F(10) > D(6) ,F(10) > C(5) , so no updating .

Ok ,Next G. Whichcan reach D,E,F,H,I,J

G(15)>=E(15),G(15)>D(6),G(15) > F(10) .So No need update .now let's see how about H,I,J

G(15) + 3 < H(25)

G(15) + 5 <I(21)

J(30) is new added

so update them.

Next ,Take H. whichcan reach E,G,J

H(18) >E(15)=G(15) .No updating .

H(18) + 14 > J(30), also no updating .

Next ,Take I. CanReach F,G,J

I(20) >F(10),I(20)>G(15) , no updating

Let's see J

I(20) + 8 < J(30)

so update J(30)-> J(28)

Last ,Add J ,CanReach G,H,I

but J(28) >G(15),

J(28) > H(18),

J(28) > I(20)

so no updating .