0
$\begingroup$

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:

enter image description here

This is my attempt.

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

enter image description here

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

enter image description here

Is it correct?

$\endgroup$
4
  • 2
    $\begingroup$ Seems fine to me. $\endgroup$
    – user1121211
    Dec 17, 2022 at 8:15
  • $\begingroup$ I also attached the table of distances $\endgroup$
    – Mark
    Dec 17, 2022 at 8:43
  • 1
    $\begingroup$ 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! $\endgroup$
    – Koen Zeven
    Dec 17, 2022 at 13:03
  • $\begingroup$ Thank you all very much! $\endgroup$
    – Mark
    Dec 17, 2022 at 18:13

1 Answer 1

Reset to default
2
$\begingroup$

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

You can use Mathematica to verify the correctness of your answer.

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

enter image description here

Your answer is correct.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .