I'm trying to implement Floyd-Warshall algorithm (all pairs shortest path). In the code below, when I enter some numbers, it gives the last number as input. I know the code is not complete.
Now what should I do to print shortest paths for each i and j? Or what do you suggest to me to do to complete this code. Thanks.
private void button10_Click(object sender, EventArgs e)
{
string ab = textBox11.Text;
int matrixDimention = Convert.ToInt32(ab);
int[,] intValues = new int[matrixDimention, matrixDimention];
string[] splitValues = textBox9.Text.Split(',');
for (int i = 0; i < splitValues.Length; i++)
intValues[i / (matrixDimention), i % (matrixDimention)] = Convert.ToInt32(splitValues[i]);
string displayString = "";
for (int inner = 0; inner < intValues.GetLength(0); inner++)
{
for (int outer = 0; outer < intValues.GetLength(0); outer++)
displayString += String.Format("{0}\t", intValues[inner, outer]);
displayString += Environment.NewLine;
}
int n = (int)Math.Pow(matrixDimention, 2);
string strn = n.ToString();
MessageBox.Show("matrix"+strn+ "in" + strn + "is\n\n\n" +displayString);
////before this line i wrote the codes to get the numbers that user enter in textbox and put it in an 2d array
for (int k = 1; k < n+1; k++)
for (int i = 1; i < n+1; i++)
for (int j = 1; j < n+1; j++)
if (intValues[i, j] > intValues[i, k] + intValues[k, j])
{
intValues[i, j] = intValues[i, k] + intValues[k, j];
string str_intvalues = intValues[i, j].ToString();
MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
}
else
{
string str_intvalues = intValues[i, j].ToString();
MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
}
}
To be on a same page, let me show you the Floyd-Warshall algorithm first:
Let us have a graph, described by matrix D
, where D[i][j]
is the length of edge (i -> j)
(from graph's vertex with index i
to the vertex with index j
).
Matrix D
has the size of N * N
, where N
is total number of vertices in graph, because we can reach the maximum of paths by connecting each graph's vertex to each other.
Also we'll need matrix R
, where we will store shortest paths (R[i][j]
contains the index of a next vertex in the shortest path, starting at vertex i
and ending at vertex j
).
Matrix R
has the same size as D
.
The Floyd-Warshall algorithm performs these steps:
initialize the matrix of all the paths between any two pairs or vertices in a graph with the edge's end vertex (this is important, since this value will be used for path reconstruction)
for each pair of connected vertices (read: for each edge (u -> v)
), u
and v
, find the vertex, which forms shortest path between them: if the vertex k
defines two valid edges (u -> k)
and (k -> v)
(if they are present in the graph), which are together shorter than path (u -> v)
, then assume the shortest path between u
and v
lies through k
; set the shortest pivot point in matrix R
for edge (u -> v)
to be the corresponding pivot point for edge (u -> k)
Now that we are on a same page with definitions, algorithm can be implemented like this:
// Initialise the routes matrix R
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
R[i][t] = t;
}
}
// Floyd-Warshall algorithm:
for (int k = 0; k < N; k++) {
for (int u = 0; u < N; u++) {
for (int v = 0; v < N; v++) {
if (D[u, v] > D[u, k] + D[k, v]) {
D[u, v] = D[u, k] + D[k, v];
R[u, v] = R[u, k];
}
}
}
}
But how do we read the matrix D
?
Let us have a graph:
In GraphViz it would be described as follows:
digraph G { 0->2 [label = "1"]; 2->3 [label = "5"]; 3->1 [label = "2"]; 1->2 [label = "6"]; 1->0 [label = "7"]; }
We first create a two-dimensional array of size 4
(since there are exactly 4
vertices in our graph).
We initialize its main diagonal (the items, whose indices are equal, for ex. G[0, 0]
, G[1, 1]
, etc.) with zeros, because
the shortest path from vertex to itself has the length 0
and the other elements with a very large number (to indicate there is no edge or an infinitely long edge between them). The defined elements, corresponding to graph's edges, we fill with edges' lengths:
int N = 4;
int[,] D = new int[N, N];
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
if (i == t) {
D[i, t] = 0;
} else {
D[i, t] = 9999;
}
}
}
D[0, 2] = 1;
D[1, 0] = 7;
D[1, 2] = 6;
D[2, 3] = 5;
D[3, 1] = 2;
After the algorithm run, the matrix R
will be filled with vertices' indices, describing shortest paths between them. In order to reconstruct the path from vertex u
to vertex v
, you need follow the elements of matrix R
:
List<Int32> Path = new List<Int32>();
while (start != end)
{
Path.Add(start);
start = R[start, end];
}
Path.Add(end);
The whole code could be wrapped in a couple of methods:
using System;
using System.Collections.Generic;
public class FloydWarshallPathFinder {
private int N;
private int[,] D;
private int[,] R;
public FloydWarshallPathFinder(int NumberOfVertices, int[,] EdgesLengths) {
N = NumberOfVertices;
D = EdgesLengths;
R = null;
}
public int[,] FindAllPaths() {
R = new int[N, N];
for (int i = 0; i < N; i++)
{
for (int t = 0; t < N; t++)
{
R[i, t] = t;
}
}
for (int k = 0; k < N; k++)
{
for (int v = 0; v < N; v++)
{
for (int u = 0; u < N; u++)
{
if (D[u, k] + D[k, v] < D[u, v])
{
D[u, v] = D[u, k] + D[k, v];
R[u, v] = R[u, k];
}
}
}
}
return R;
}
public List<Int32> FindShortestPath(int start, int end) {
if (R == null) {
FindAllPaths();
}
List<Int32> Path = new List<Int32>();
while (start != end)
{
Path.Add(start);
start = R[start, end];
}
Path.Add(end);
return Path;
}
}
public class MainClass
{
public static void Main()
{
int N = 4;
int[,] D = new int[N, N];
for (int i = 0; i < N; i++) {
for (int t = 0; t < N; t++) {
if (i == t) {
D[i, t] = 0;
} else {
D[i, t] = 9999;
}
}
}
D[0, 2] = 1;
D[1, 0] = 7;
D[1, 2] = 6;
D[2, 3] = 5;
D[3, 1] = 2;
FloydWarshallPathFinder pathFinder = new FloydWarshallPathFinder(N, D);
int start = 0;
int end = 1;
Console.WriteLine("Path: {0}", String.Join(" -> ", pathFinder.FindShortestPath(start, end).ToArray()));
}
}
You can read 'bout this algorithm on wikipedia and get some data structures generated automatically here