Algorithms on Graphs

What does Kruskal’s Algorithm do?

Find the minimum spanning tree

Kruskal’s Algorithm

1- Sort all arcs into ascending order of weight

2- Select the arc of least weight to start the tree

3- Consider the next arc of least weight. If it creates a cycle reject it. If not, add it to the tree.

4- Repeat until all vertices are connected

What does Prim’s Algorithm do

Find the minimum spanning tree

Prim’s Algorithm

1- Select a vertex to start the tree

2- Select an arc of least weight that connects a vertex not in the tree to a vertex in the tree

3- Repeat until all vertices are connected

How to do Prim’s Algorithm on a distance matrix

1- Choose any vertex to start the tree

2- Delete the row in the matrix for the chosen vertex

3- Number the column in the matrix for the chosen vertex

4- Put a ring around the lowest undeleted entry in the numbered columns

5- The ringed entry becomes the next arc in the tree

What does Dijkstra’s Algorithm do?

Find the shortest path from S to T

Dijkstra’s Algorithm

1- Label the start vertex S with final label 0

2- Record a working value (final label + weight of arc) at every vertex that is connected to the vertex that has just received its final label. Only record the working value if it is smaller than the current value at the vertex

3- Look at all vertices without final labels. Select the one with the smallest working value and make this the final label.

4- Repeat until T receives its final label

5- Trace back from T to S, vertices on the path will have a final label such that the previous final label - the weight of the arc = the final label