Tag Archives: vertex

Floyd-Warshall Shortest Paths

The Floyd Warshall algorithm is an all pairs shortest paths algorithm. This can be contrasted with algorithms like Dijkstra’s which give the shortest paths from a single node to all other nodes in the graph.

Floyd Warshall’s algorithm works by considering first the edge set of the graph. This is the set of all paths of the graph through one edge. Node pairs that are connected to one another through an edge will have their shortest path set to the length of that edge, while all other node pairs will have their shortest path set to infinity. The program then runs through every triplet of nodes (i, j, k) and checks if the path from i to k and the path from k to j is shorter than the current path from i to j. If so, then the distance and the path is updated.

So lets consider an example on the graph in the image above. The edge set of this graph is E = {(0, 1), (0, 2), (0, 3), (1, 3), (3, 4)}. So our initial table is:

  0 1 2 3 4
0 inf (0, 1) (0, 2) (0, 3) inf
1 (0, 1) inf inf (1, 3) inf
2 (0, 2) inf inf inf inf
3 (0, 3) (1, 3) inf inf (3, 4)
4 inf inf inf (3, 4) inf

As we look to update the paths, we first look for routes that go through node 0:

Because node 0 connects to both node 1 and node 2, but node 1 does not connect to node 2, we have the following truth holding in the matrix above:
cost(0, 1) + cost(0, 2) < cost(1, 2), so we can update the shortest path from node 1 to node 2 to be (1, 0, 2).

Because node 0 connects to both node 2 and node 3, but node 2 does not connect to node 3, we have the following truth holding in the matrix above:
cost(0, 2) + cost(0, 3) < cost(2, 3), so we can update the shortest path from node 2 to node 3 to be (2, 0, 3).

Because node 3 connects to both node 0 and node 4, but node 0 does not connect to node 4, we have the following truth holding in the matrix above:
cost(0, 3) + cost(3, 4) < cost(0, 4), so we can update the shortest path from node 0 to node 4 to be (0, 3, 4).

Because node 3 connects to both node 1 and node 4, but node 1 does not connect to node 4, we have the following truth holding in the matrix above:
cost(1, 3) + cost(3, 4) < cost(1, 4), so we can update the shortest path from node 1 to node 4 to be (1, 3, 4).

Because node 3 connects to both node 2 and node 4, but node 2 does not connect to node 4, we have the following truth now holding:
cost(2, 3) + cost(3, 4) < cost(2, 4), so we can update the shortest path from node 2 to node 4 to be (2, 0, 3, 4).

The final table giving the list of shortest paths from every node to every other node is given below.

  0 1 2 3 4
0 inf (0, 1) (0, 2) (0, 3) (0, 3, 4)
1 (0, 1) inf (1, 0, 2) (1, 3) (1, 3, 4)
2 (0, 2) (1, 0, 2) inf (2, 0, 3) (2, 0, 3, 4)
3 (0, 3) (1, 3) (2, 0, 3) inf (3, 4)
4 (0, 3, 4) (1, 3, 4) (2, 0, 3, 4) (3, 4) inf

To see more examples and to help answer questions, check out the script in my examples section on the Floyd-Warshall algorithm

Kruskal’s Algorithm

I’ve just written a script that executes Kruskal’s algorithm on a randomly generated graph.

Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. These have several applications in areas like transportation and the network simplex method. We already discussed Prim’s algorithm. Another method for generating minimum spanning trees is Kruskal’s algorithm. A spanning tree is a subset of the edges of a graph that connects to every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.

Kruskal’s algorithm works by the following procedure.
1. Initially each vertex is a stand-alone tree, so for each v in V, we define the tree Treev = {v}. The set of selected edges E* is initially empty.
2. Find the edge e = (uv) of minimum weight such that u and v belong to different trees. If no such edge exists, go to 6.
3. Merge the trees Tlookup(u) and Tlookup(v).
4. Add the edge e to E* and remove the edge e from the graph.
5. If the size of E* is less than n – 1, go to step 2. Else go to step 7.
6. If you reached this step. then the graph is not connected.
7. If you reached this step, then E* is a minimum spanning tree.

For example, consider the graph represented by the following adjacency matrix:

0 1 2 3 4
0 13 12
1 16
2 24
3 13 13
4 12 16 24 13

Graph with 5 nodes

Initially we have 5 distinct trees and E* = {}/
T0 = {0}
T1 = {1}
T2 = {2}
T3 = {3}
T4 = {4}.

The first step of Prim’s algorithm says to find the cheapest edge such that its two endpoints belong to different trees. This will be the edge (0, 4) with a cost of 12. So E* = {(0, 4)}. We then merge the two trees so that our trees are now:
T0 = {0, 4}
T1 = {1}
T2 = {2}
T3 = {3}

Again, we look for the cheapest edge such that the endpoints of the two edges are in different trees. There are two edges with a cost of 13 (either (0, 3) or (3, 4)) so we will arbitrarily choose (0, 3) and add it to our tree. So E* = {(0, 4), (0, 3)}. We again merge the associated trees and it results in the following trees:
T0 = {0, 3, 4}
T1 = {1}
T2 = {2}

The cheapest edge that has endpoints in distinct trees will be the edge (1, 4) with a cost of 16. We add this edge to our tree. So E* = {(0, 4), (0, 3), (1, 4)}. Once we merge the associated trees we have the following:
T0 = {0, 1, 3, 4}
T2 = {2}

The cheapest remaining edge that has endpoints in distinct trees will be the edge (2, 4) with a cost of 16. This makes E* = {(0, 4), (0, 3), (1, 4), (2, 4)}. We merge the associated trees and arrive at:
T0 = {0, 1, 2, 3, 4}

Because T0 contains all the nodes in the graph it is a spanning tree. Its total cost is 12 + 13 + 16 + 24 = 65.

To learn more and see more examples, view Kruskal’s Algorithm at LEARNINGlover.com

Prim’s Algorithm

I have just written a script that executes Prim’s Algorithm that finds the minimum spanning tree on a randomly generated graph.

Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. This has many applications including the very important network simplex method. Prim’s algorithm is a greedy method which does finds this MST. A spanning tree is a subset of the edges of a graph that connects every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.

Prim’s algorithm works by the following procedure.
1. Let Treev be the set of vertices included in the tree, and TreeE be the set of edges included in the tree. Initially Treev and TreeE are empty.
2. Add an arbitrary vertex to Treev (TreeE is still empty).
3. Find the edge e of minimum weight such that one vertex is in Treev and vertex is not in Treev. Add the associated vertex to Treev, and add e to TreeE.
4. If edge was found in step 3, goto 5, else go to 6.
5. If the number of vertices in Treev is less than the number of vertices in the original graph, then the graph is not connected and thus does not contain a minimum spanning tree. Goto 8.
6 If the number of vertices in Treev is less than the number of vertices in the original graph, go to 2, else go to 7.
7. Output “The Minimum Spanning Tree is “, TreeE.
8. Output “This graph does not have a minimum spanning tree because it is not connected. ”

For example, consider the graph represented by the following adjacency matrix:

0 1 2 3 4
0 13 12
1 16
2 24
3 13 13
4 12 16 24 13

Graph with 5 nodes

Initially our tree (Tv is empty). The first step says to choose a random vertex and add it to the tree, so lets choose vertex 2.

Iteration 1: Now our tree contains the vertex 2 (i.e. Tv = {2}) and likewise TE contains the edges coming from Tv. Thus TE = {(2, 4)}.
We want to choose the cheapest edge that has one endpoint in Tv and one endpoint not in Tv. These edges are represented by TE. Notice that TE only contains one edge, so we select this
edge, which has a cost of 24.

Iteration 2: Our tree thus contains the vertices 2 and 4 (i.e Tv = {2, 4}) and likewise TE contains the edges coming from Tv. Thus TE = {(0, 4), (1, 4), (3, 4)}.
Again, we want to choose the cheapest edge that has one endpoint in Tv and one endpoint not in Tv. This will be the edge (0, 4) which has a cost of 12.

Iteration 3: Now Tv = {0, 2, 4} and TE = {(1, 4), (3, 4), (0, 3)}. The cheapest of these three edges is the edge (0, 3) with a cost of 13, which means we will add it to our tree.

Iteration 4: Now Tv = {0, 2, 3, 4} and TE = {(1, 4)}. Since (1, 4) is the only edge connected to our tree we add it and it has a cost of 16.

Iteration 5: Now Tv = {0, 1, 2, 3, 4} and TE = {}. Because our tree contains all the vertices of the graph it is now spanning tree. The cost of this spanning tree is 24 + 12 + 13 + 16 = 65.

To learn more and see more examples, view Prim’s Algorithm at LEARNINGlover.com