# Exercise on Dijkstra's algorithm

I would like to build, applying Dijkstra's algorithm, all paths of least weight starting from s and arriving at every other vertex of the graph:

This is my attempt.

The distance values are shown in the following table for each step of the algorithm:

The resulting shortest path from s is marked in blu in the following graph:

Is it correct?

• Seems fine to me.
– user1121211
Dec 17, 2022 at 8:15
• I also attached the table of distances
– Mark
Dec 17, 2022 at 8:43
• Only minor issue is step 6 where you did not update "c" to be 16 (i.e. d -> c will have distance 10 + 6 =16), but it does not matter for the end result. Looks good! Dec 17, 2022 at 13:03
• Thank you all very much!
– Mark
Dec 17, 2022 at 18:13

It is an easy question, you can implement Dijkstra's algorithm in any perferred programming language.

g = Graph[{s -> a, s -> e, s -> f, a -> b, a -> d, a -> e, a -> f,
b -> c, d -> b, d -> c, e -> c, e -> d, f -> d, f -> e},
EdgeWeight -> {3, 10, 5, 11, 8, 6, 6, 3, 2, 6, 13, 3, 5, 5},
VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"]

Table[HighlightGraph[g, PathGraph@FindShortestPath[g, s, All][v]], {v,
VertexList[g]}]

{GraphDistanceMatrix[g] // MatrixForm, VertexList[g]}



The graph distance matrix is