Chapter 3 - Algorithms on Graphs

• Kruskal's Algorithm - Sort arcs into ascending weight, then pick the arcs in order, remove any that make a cycle, continue adding until all vertices are connected
• Prims Algorithm - Choose any vertex to start the tree, select the arcs of least weight, carry on doing this until all edges are connected and there are no cycles
• Dijkstra's Algorithm - Finds shortest path between any 2 vertices, you can use Dijkstra's on a digraph
• Floyd's Algorithm - Finds shortest paths between every pair of vertices in a network