It's UWAweek 47

help3001

This forum is provided to promote discussion amongst students enrolled in CITS3001 Advanced Algorithms.

Please consider offering answers and suggestions to help other students! And if you fix a problem by following a suggestion here, it would be great if other interested students could see a short "Great, fixed it!"  followup message.

How do I ask a good question?
Displaying selected article
Showing 1 of 202 articles.
Currently 4 other people reading this forum.


 UWA week 38 (2nd semester, week 8) ↓
SVG not supported

Login to reply

👍?
helpful
8:25am Thu 19th Sep, Max WG.

I want to add to Gozz's answer. Spanning trees are unrooted undirected trees. Shortest path trees are directed and rooted by construction, and only need to cover nodes that are reachable from the source node. The directed version of a spanning tree is an arborescence. Finding a spanning arboresence is much more complicated than finding a spanning tree: [see here](https://en.wikipedia.org/wiki/Edmonds%27_algorithm). The point is that spanning trees only work on undirected graphs, and shortest path trees work on both directed and undirected graphs. If you run Dijkstra's on an undirected graph, then they're still not always the same thing as Gozz points out.

The University of Western Australia

Computer Science and Software Engineering

CRICOS Code: 00126G
Written by [email protected]
Powered by history
Feedback always welcome - it makes our software better!
Last modified  8:08AM Aug 25 2024
Privacy policy