The Prufer Code and the Floyd-Warshall Algorithm - Floyd-Warshall Algorithm
(Page 4 of 4 )
Before I leave you for today, I want to present another simple algorithm. It is the Floyd-Warshall algorithm. This algorithm will in essence tell you between which vertexes a road exists. The idea is simple; we start one iteration and go through point to point, and if from point "i" to "j" there exists a road, and from "j" to "k" also, then we can conclude that from point "i" to "k" there exists a road as well.
The algorithm works with an adjacency matrix, where mat[i][j] is one if there exists an edge between "i" and "j". In the end, mat[i][j] will be one if there exists a road between "i" and "j," and zero otherwise.
If we would make these checks in the right order, a single iteration should be enough; however, determination of this order is hard, so we will execute the upper theory as long as it assures that we will find all connection between the vertexes. It is proved that n times will suffice in a graph with n vertexes.
The code snippet in C:
for( i=0; i <n; ++i)
for( j =0; j < n;++j)
for ( k =0; k < n; ++k)
if(mat[i][k] && mat[k][j])
mat[i][j] = 1;
We can use this code for determination if, inside a graph, there is a circle, for instance. If at the end on the main diagonal of the matrix, we find one, that means that there exists a road from a point to the same point -- which in practice means a circle. This is a very slow way to determine this (there are much better solutions, as we will find out), yet it is a possible solution.
If we choose to save the distances between the vertexes, and when we make the check, the new value will be the distance between "i" to "j" plus "j" to "k," we will find out the distance in number of edges between the vertexes in the end matrix.
Here is a little C++ program that uses this algorithm to tell if there exists a circle and answers a couple of other, more general questions about graphs, like finding the vertex with the most incoming or outgoing edges, the isolated vertexes, vertexes which have only incoming edges, vertexes which have only outgoing edges, and vertexes which have edges in both directions.
Download Source
The code is simple and should be perfect for illustrating the use of the adjacency matrix. Feel free to skim through it and learn from it. Thank you for reading up to this point; I invite you to come back next time for the next chapter of this series about graphs. Rating this article is appreciated, as is posting your thoughts and comments here on the blog. Until we meet again, Live With Passion!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
