Monthly Archives: August 2011

Examples

Bellman-Ford Algorithm

Leave a comment

I just finished a script which executes the Bellman-Ford Algorithm on a randomly generated directed graph (possibly with negative arcs). It can be accessed here.

The Bellman Ford algorithm is another shortest path algorithm. Unlike Dijkstra’s algorithm, though, this algorithm can handle edges with negative weights and detect negative cycles in a graph. Negative cycles are important because in a graph with negative cycles, there is no shortest path to some nodes since a negative cycle can be iterated an infinite number of times.

The algorithm works by initially setting the distance from the source node to all other nodes to be infinity. The distance to the source is then updated to be 0 since we are already there.
Next we proceed through each edge (u, v) and check the condition that if the distance to u plus the weight of the edge (u, v) is less than the distance to the node v, then we have just found a shorter route to v.

This condition on the edges only needs to be checked at most |V| times for each edge since any path will contain at most |V| edges, which means that the distance of a node can be updated at most |V| times.

If after |V| times there is still a node whose weight can be updated, it signifies the existence of a negative weight cycle and the Bellman-Ford will show that this cycle exists, but will be unable to find shortest paths in this problem as shortest paths no longer exist.

 

Blog, Examples

Dijkstra’s Algorithm

Leave a comment

I’ve just written a script that executes Dijkstra’s algorithm that seeks to find the shortest path tree on a randomly generated graph.

Given a weighted graph G and a vertex s, the single node shortest path problem seeks to find the shortest path from s to every other vertex in this graph such that the sum of the weights of the edges along these paths is minimized. One famous algorithm for this problem is Dijkstra’s Algorithm, which constructs this shortest path tree using techniques of greedy algorithms and dynamic programming.

Dijkstra’s Algorithm works as follows.

  • Initially we have an empty path tree T, and assume that the distance to every vertex in the graph has some maximum cost, say infinity, i.e. w(v) = infinity for all v in V.
  • Add the node s to the tree, and give the associated path cost a value of zero, i.e. w(s) = 0.
  • Find the edge which is adjacent to T that adds the vertex whose cost is minimum, i.e. we look for an e = (u, v) such that u is in T, and v is not in T and w(u) + cost(u, v) < w(v) is minimum. If no such edge exists go to 5.
  • Add the corresponding edge and vertex to the tree, and update the weight vector of the vertex v. Go to 3.
  • The path tree T now represents the shortest path from the vertex s to all other vertices reachable in the graph G. The weight vector w represents the costs of these paths.

For an example of Dijkstra’s algorithm executed on the Graph with the following adjacency matrix:

01234567
0––24––20–
1–––111175–
22–––10–7–
3411–––––2
4–1110–––––
5–7–––––14
62057–––––
7–––2–14––

Graph with 8 Nodes

Suppose we are interested in discovering the shortest paths from the node 0.

Initially Dijkstra’s algorithm constructs an empty path tree, T = {}.

Because we want to discover the shortest paths from the node 0, our first step will be to add this node to the tree and update the weight vector.
T = {0}
w(0) = 0.

Now we will consider the edges adjacent to T, {(0, 2), (0, 3), and (0, 6)}. Our assumption is that the shortest path of every vertex in T has already been computed correctly and we will seek the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T. The edge that does that currently is (0, 2) since w(0) = 0 and c(0, 2) = 2. We add the node 2 to T and update the weight vector.
T = {0, 2}
w(2) = 2.

The edges adjacent to T are now {(0, 3), (0, 6), (2, 4), (2, 6)}.
The associated path costs are:
w(0) + c(0, 3) = 0 + 4 = 4
w(0) + c(0, 6) = 0 + 20 = 20
w(2) + c(2, 4) = 2 + 10 = 12
w(2) + c(2, 6) = 2 + 7 = 9
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (0, 3). We add the node 3 to T and update the weight vector.
T = {0, 2, 3}
w(3) = 4

The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (3, 7)}.
The associated path costs are:
w(0) + c(0, 6) = 0 + 20 = 20
w(2) + c(2, 4) = 2 + 10 = 12
w(2) + c(2, 6) = 2 + 7 = 9
w(3) + c(3, 1) = 4 + 11 = 15
w(3) + c(3, 7) = 4 + 2 = 6
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (3, 7). We add the node 7 to T and update the weight vector.
T = {0, 2, 3, 7}
w(7) = 6

The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (5, 7)}.
The associated path costs are:
w(0) + c(0, 6) = 0 + 20 = 20
w(2) + c(2, 4) = 2 + 10 = 12
w(2) + c(2, 6) = 2 + 7 = 9
w(3) + c(3, 1) = 4 + 11 = 15
w(7) + c(5, 7) = 6 + 14 = 20
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 6). We add the node 6 to T and update the weight vector.
T = {0, 2, 3, 6, 7}
w(6) = 9

The edges adjacent to T are now {(2, 4), (3, 1), (5, 7) (6, 1)}.
The associated path costs are:
w(2) + c(2, 4) = 2 + 10 = 12
w(3) + c(3, 1) = 4 + 11 = 15
w(7) + c(5, 7) = 6 + 14 = 20
w(6) + c(6, 1) = 9 + 5 = 14
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 4). We add the node 4 to T and update the weight vector.
T = {0, 2, 3, 4, 6, 7}
w(4) = 12

The edges adjacent to T are now {(3, 1), (5, 7), (6, 1), (4, 1)}.
The associated path costs are:
w(3) + c(3, 1) = 4 + 11 = 15
w(7) + c(5, 7) = 6 + 14 = 20
w(6) + c(6, 1) = 9 + 5 = 14
w(4) + c(4, 1) = 12 + 11 = 23
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (6, 1). We add the node 1 to T and update the weight vector.
T = {0, 1, 2, 3, 4, 6, 7}
w(1) = 14

The edges adjacent to T are now {(5, 7), (1, 5)}.
The associated path costs are:
w(7) + c(5, 7) = 6 + 14 = 20
w(1) + c(1, 5) = 14 + 7 = 21
We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (5, 7). We add the node 5 to T and update the weight vector.
T = {0, 1, 2, 3, 4, 5, 6, 7}
w(5) = 20

Now that T contains all the nodes from the tree, we know the shortest path from node 0 to all other nodes and and have solved the problem. The associated weight vector is w = [0, 14, 2, 4, 12, 20, 9, 6].

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

Blog, Examples

Kruskal’s Algorithm

1 Comment

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 = (u, v) 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:

01234
0–––1312
1––––16
2––––24
313–––13
412162413–

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

Blog, Examples

Prim’s Algorithm

Leave a comment

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:

01234
0–––1312
1––––16
2––––24
313–––13
412162413–

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

Blog, Examples

Gaussian Elimination

Leave a comment

I have just written a script which executes the Gaussian Elimination Algorithm.

When we have a collection of lines we wish to know if they all intersect at some point. Many times we are interested in determining what that point is. In order to calculate this information, we first need an understanding of the lines themselves. The way the Gaussian Elimination Algorithm works is that the collection of lines are input using a notation of Ax = b, where the matrix A is called the coefficient matrix, as the nth row of it corresponds to the coefficients for the nth line being considered. The vector b represents the right hand side vector (in two dimensions, we would call these constants the y-intercepts of the lines. In higher dimensions they hold a similar property). The vector x represents the point where the lines intersect. It is this quantity which Gaussian Elimination seeks to determine.

The basic procedure of Gaussian Elimination is to use \”elementary row operations\” on the matrix (A|b), which is called the augmented matrix, to transform A into upper triangular form. Once this is done, a procedure called back-substitution can find the solution (x) to this problem.

The elementary row operations that we are allowed to perform are:

  • Interchange two rows.
  • Multiply a row by a nonzero number.
  • Add a row to another one multiplied by a number.

    • For the last property listed above, we will determine this number by dividing the coefficient of the term we which to eliminate by the negative of the coefficient of the element on the main diagonal of the same column of the matrix. This will have the property of cancelling out, or producing a desired zero in the resulting row.

    If this algorithm produces an upper triangular matrix from which we can solve for x using back-substitution. This procedure of back-substitution is simply solving for the vector x from the bottom of the matrix to the top. If the algorithm does not produce an upper triangular matrix (because somewhere along the line, we are unable to obtain a ratio because we have zero’s on the diagonal and all zeros below the diagonal), then we say the matrix is singular. This means that there is no unique point where the lines all intersect.

    To learn more and see more examples, check out My Script on Gaussian Elimination.