How to output the shortest path in Floyd-Warshall algorithm?

Question

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);
                }
}

Solution 1

When you are using Floyd algorithm, it saves only the shortest distance from node i to node j of your graph. So, you can also save the path to nodes. How to do it?

one of the ways to implement it - is to save the parent (the node, which is a previous node for current node in the path) node. You are to make another matrix, which will contain paths. It could look like this:

int[,] pathS = new int[matrixDimention, matrixDimention];
for (int i = 0; i < splitValues.Length; i++){
    intValues[i / (matrixDimention), i % (matrixDimention)] = Convert.ToInt32(splitValues[i]);
    pathS[i / (matrixDimention), i % (matrixDimention)] = -1;    
}
.....
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];
                pathS[i,j] = k;
                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);
            }

Now you have additional pathS array, which contains intermidiate paths between nodes i and j. For better understandning you should consider, that pathS[i,j] is a node between this two nodes (e.g. i -> [k] -> j). But your path could be longer, than 3 nodes (that's why I wrote node k in [] braces). So, now you have to check path between i and k - pathS[i,k] and path between k and j - pathS[k,j]. And do the same recursively, until pathS between some i and j equals to "-1".

Solution 2

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:

1. 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)

2. 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