Floyd's Algorithm Explanation

Question

Concerning

floyds(int a[][100],int n).

What does 'a' and represent and what does each of the two dimensions of a represent?

What does 'n' represent?

I have a list of locations, with a list of connections between those locations and have computed the distance between those connections that are connect to each other. Now I need to find shortest path between any given two locations (floyd's) - but need to understand how to apply floyds(int a[][100],int n) to my locations array, city dictionaries, and connection arrays.

FYI - Using objective C - iOS.

Answer 1

n is the number of nodes in the graph.

a is an distance matrix of the graph. a[i][j] is the cost (or distance) of the edge from node i to node j.

(Also read the definition of adjacency matrix if you need more help with the concept.)

Answer 2

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j

2    (infinity if there is none).

3    Also assume that n is the number of vertices and edgeCost(i,i) = 0

4 */

5

6     int path[][];

7     /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path

8        from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to

9        edgeCost(i,j).

10     */

12     procedure FloydWarshall ()

13        for k := 1 to n

14           for i := 1 to n

15              for j := 1 to n

16                 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

http://en.wikipedia.org/wiki/Floyd-Warshall

wiki is very good~~~

Answer 3

floyd-warshall(W) // W is the adjacent matrix representation of graph..
 n=W.rows;
 for k=1 to n
    for i=1 to n
       for j=1 to n
            w[i][j]=min(W[i][j],W[i][k]+W[k][j]);
 return W;

It's a dp-algorithm.At the k-th iteration here W[i][j] is the shortest path between i and j and the vertices of the shortest path(excluding i and j) are from the set {1,2,3...,k-1,k}.In min(W[i][j],W[i][k]+W[k][j]), W[i][j] is the computed shortest path between i and j at k-1-th iteration and here since the intermediate vertices are from the set {1,2...k-1},so this path does not include vertex k. In W[i][k]+W[k][j],we include vertex k in the path.whichever between the two is minimum is the shortest path at k-th iteration. Basically we check that whether we should include vertex k in the path or not.