TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 22

Use one of the algorithms presented in the lecture to construct a spanning tree which contains all the shortest paths connecting vertex x with all the other vertices in the graph of Exercise 21.

Solution

We use the solution of Dijkstra's algorithm from Exercise 21 to construct the spanning tree, which contains all shortest paths connecting the node x. We just use all the edges between nodes and their predecessors and get the following tree:

Materialien

Neues Material hinzufügen

E

• Exercise 22 - Tree.png (details)