Chapter 3 - Algorithms on graphs

minimum spanning tress

spanning tress such that the total length of its arcs is as small as possible

what can you use kruskals algorithm for

to find a minimum spanning tree

kruskals algorithm

• sort all arcs into ascending order of weight

• select the arc of least weight to start the tree

• then add arcs in order of ascending weight unless an arc would form a cycle then reject it

what can you use prims algorith for

to find minimum spanning tree

prims algorithm

• choose any vertex to start the tree

• then select an arc of least weight that joins a vertex already in the tree to a vertex not yet in the tree repeat till all vertices are connected

prims algorithm for distance matric

• choose any vertex to start the tree

• delete the row in the matrix for the chosen vertex

• number the column in the matrix for the chosen vertex

• put a ring round the lowest undeleted entry in the numbered columns

• the ringed entry becomes the next arc to be added to the tree

• repeat till all rows have been deleted

whats dijkstras algorithm used for

to find shortest path between 2 vertices in a network

dijkstras algorithm

what can you use floyds algorith mfor

to find shortest path between every pair of vertices

floyds algorithm