algorithms on graphs Flashcards
what’s a minimum spanning tree?
a spanning tree such that the total length of its arcs is as small as possible
describe the process for Kruskal’s algorithm
- sort arcs into ascending weight
- start with arc of lowest weight
- continue to add arcs of next lowest weight if it does not form a cycle
which algorithms can be used to find a minimum spanning tree?
Kruskal’s
Prim’s
describe Prim’s algorithm
- choose any vertex to start tree
- select an arc of least weight that joins a vertex already in the tree to a vertex not yet in the tree
- repeat 2
what is the difference between Prim’s and Kruskal’s agorithms?
Prim’s considers vertices
Kruskal’s considers edges
which algorithm adds arcs to vertices that must already be in the tree?
Prim’s
Which algorithm adds arcs to a MST in ascending order of weight?
Kruskal’s
Does Prim’s or Kruskal’s algorithm have a distance matrix version?
Prim’s
What does Dijkstra’s algorithm find?
the shortest path through a network from the start to another vertex
Is it possible to use Dijkstra’s algorithm on networks with directed arcs?
yes
Why might Floyd’s algorithm be more useful than Dijkstra’s?
Floyd’s’ can find the shortest path between ANY PAIR of vertices
what does Floyd’s algorithm find?
the shortest path between any pair of vertices in a network
which algorithm uses distance tables and route tables?
Floyd’s algorithm
how do you do Floyd’s algorithm?
complete distance tables and route tables and iterate these
a network with n vertices produces two tables as a result of n iterations
what do the tables in Floyd’s algorithm show?
one table shows the shortest distances
and the other contains information about the corresponding paths taken
