Question

Correction: in question - There two 'e' nodes. So name the middle one as 'e'. So the node that 'c' points to is 'd' instead of 'e'

Use Dijkstra's Algorithm to solve single source shortest path problem for the graph given below. Use vertex 'a' as the start node. It will be useful to build a table as explained in class. elow. Use vertex 'a' as the start node. It will be useful to build a 4 4 6

Answer 1

WITH INFERENCE FROM YOUR LAST LINE, WHICH STATES THAT THE NODE THAT C POINTS TO IS D, HENCE THE FIGURE MUST LOOK LIKE THIS:

4 4

SINCE WE START WITH VERTEX 'A' AS GIVEN IN THE QUESTION, WE WILL LOOK FOR THE EDGE HAVING THE LEAST DISTANCE FROM A:

SO THE GRAPH NOW LOOKS LIKE:

NOW FROM VERTEX B WE FIND THE EDGE WITH THE LOWEST DISTANCE:

INFINITE0 4 INFINITE INFINITE

HENCE THE GRAPH WILL NOW LOOK LIKE THIS:

NOW WE WILL FIND THE EDGE ORIGINATING FROM VERTEX C WITH THE SHORTEST PATH, HENCE:

INFINITE INFINITE0 6 INFINITE

HENCE THE NEW GRAPH WILL LOOK LIKE THIS:

4 6 3

NOW WE WILL FIND THE EDGE ORIGINATING FROM VERTEX D WITH THE SHORTEST PATH, HENCE:

INFINITE 2 INFINITE 0 4

SINCE TAKING THE PATH FROM D TO B WILL TAKE US BACK AND FORM A CYCLE, HENCE THE PATH D TO E IS CHOSEN, HENCE THE GRAPH LOOKS LIKE THIS :

4. 4

THIS IS THE SHORTEST PATH.