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$ Commented Dec 17, 2022 at 8:15
  • $\begingroup$ I also attached the table of distances $\endgroup$ Commented 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$ Commented Dec 17, 2022 at 13:03
  • $\begingroup$ Thank you all very much! $\endgroup$ Commented 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.