Is the shortest path using Dijkstra's Algorithm symmetric?

Question

I am writing a code for finding the shortest path using Dijkstra's algorithm for an unweighted graph. I am wondering if this shortest path is symmetric i.e. if the shortest path from say A->E is A->D->F->E does it also mean that the shortest path from E->A should be E->F->D->A using Dijkstra's algorithm

  | A   |   B   |   C   |   D   |   E   |   F   |   G   |   H   |   I   |   J   |   

----------------------------------------------------------------------------------------------------------------------------------------------------------------

A | 0   |   17  |   15  |   29  |   41  |   27  |   31  |   24  |   6   |   46  |

B | 17  |   0   |   40  |   48  |   32  |   24  |   47  |   47  |   50  |   22  |

C | 15  |   40  |   0   |   49  |   1   |   2   |   24  |   23  |   19  |   38  |

D | 29  |   48  |   49  |   0   |   27  |   46  |   29  |   33  |   14  |   32  |

E | 41  |   32  |   1   |   27  |   0   |   40  |   11  |   2   |   22  |   33  |

F | 27  |   24  |   2   |   46  |   40  |   0   |   27  |   25  |   18  |   25  |

G | 31  |   47  |   24  |   29  |   11  |   27  |   0   |   34  |   50  |   10  |

H | 24  |   47  |   23  |   33  |   2   |   25  |   34  |   0   |   21  |   24  |

I | 6   |   50  |   19  |   14  |   22  |   18  |   50  |   21  |   0   |   15  |

J | 46  |   22  |   38  |   32  |   33  |   25  |   10  |   24  |   15  |   0   |

Find the shortest path between (seperate vertice with comma e.g A, B represents A to B): A,E
The shortest path is A->I->E and the weight is 28.0


Find the shortest path between (seperate vertice with comma e.g A, B represents A to B): E,A
The shortest path is E->C->A and the weight is 16.0

Answer 1

Warning: The numbers below were calculated by hand, so there might be mistakes or typos; take them with grain of salt!

The path A->I->E your implementation found is not the shortest one. I'll refer to the pseudocode from Wikipedia:

• In the first iteration of the while loop, we look at vertex A which has distance $0$ and adjust the array dist array which becomes identical to the first row of your matrix.

  | A | B  | C  | D  | E  | F  | G  | H  | I  | J  |   
  | 0 | 17 | 15 | 29 | 41 | 27 | 31 | 24 | 6  | 46 |
  

• The second iteration picks vertex I with distance $6$, since that is the smallest one among the unprocessed ones. The dist array will be updated,using I as a shortcut whenever possible (e.g. for C or D, but not for B):

  | A | B  | C  | D  | E  | F  | G  | H  | I  | J  |   
  | 0 | 17 | 15 | 20 | 28 | 24 | 31 | 24 | 6  | 21 |
  

• Third iteration picks vertex C with distance $15$, updating the distances as follows:

  | A | B  | C  | D  | E  | F  | G  | H  | I  | J  |   
  | 0 | 17 | 15 | 20 | 16 | 17 | 31 | 24 | 6  | 21 |
  

• Finally, the fourth iteration picks vertex E with distance $16$ and celebrates that it has found the shortest distance between A and E.

Your result looks more like an application of a greedy algorithm, which always takes the shortest available connection between the current point and any of its neighbours -- and this graph serves as a good example of why this approach doesn't work :-)