All-pairs Shortst Path: Floyd help

[Tigerdude]

I'm trying to write a program that uses a DIMACS Graph input, and do several diffent things with it. I've got most of the methods working except one: An all-pairs shortest path that uses Floyd's Algorithm. I've written it a couple times, and it works sometimes, throws and exception sometimes, and gets stuck in an infinite loop sometimes :cry: I've followed every single note and algorithm, and yet it still doesn't work.

I'm pretty sure the problem is related to the Path[][] variable that it returns. Any help would be much appreciated :mrgreen:

private static void floyd(Graph<City> g, double dist[][], int path[][]) throws GraphException
   {
        int i;
        int j;
        int k;
        City c1;
        City c2;

         for( i =0; i < g.size(); i++) {
           c1 = g.retrieveVertex(new City(i+1));
           for(j = 0; j < g.size(); j++) {
             c2 = g.retrieveVertex(new City(j+1));
             path[i][j] = 0;
             if ( i == j)
               dist[i][j] = 0;
             else if(g.isEdge(c2, c1) == true)
               dist[i][j] = g.retrieveEdge(c1, c2);
             else
               dist[i][j] = INFINITY;
           }
         }

        for(k = 0; k < g.size(); k ++)  {
           for( i = 0; i < g.size(); i++) {
             for(j = 0; j < g.size(); j++) {
               if (dist[i][k] != INFINITY && dist[k][j] != INFINITY) {
                if (dist[i][j] >(dist[i][k] + dist[k][j])) {
                  dist[i][j] = dist[i][k] + dist[k][j];
                  path[i][j] = k;
                }
               }
             }
           }
        }
}

[AstroNox]

Hey Tigerdude, I had read through your Floyd-Warshall implementation and I've noticed several things:

1. Did you make sure that your constant INFINITY did not coincide with any of your edge values in your graph?
2. Are you sure that your graphs do not contain any negative cycles?
3. Look at the underlined code below. Although I do not know how is your Graph class implemented, the c1 and c2 variables used in your .isEdge() and .retrieveEdge() seems "inverted". Remember that the Floyd-Warshall requires a directed graph, thus getting your directions wrong can instantly cause your algorithm to fail.

private static void floyd(Graph<City> g, double dist[][], int path[][]) throws GraphException
   {
        int i;
        int j;
        int k;
        City c1;
        City c2;

         for( i =0; i < g.size(); i++) {
           c1 = g.retrieveVertex(new City(i+1));
           for(j = 0; j < g.size(); j++) {
             c2 = g.retrieveVertex(new City(j+1));
             path[i][j] = 0;
             if ( i == j)
               dist[i][j] = 0;
             [U]else if(g.isEdge(c2, c1) == true)[/U]
               [U]dist[i][j] = g.retrieveEdge(c1, c2);[/U]
             else
               dist[i][j] = INFINITY;
           }
         }

        for(k = 0; k < g.size(); k ++)  {
           for( i = 0; i < g.size(); i++) {
             for(j = 0; j < g.size(); j++) {
               if (dist[i][k] != INFINITY && dist[k][j] != INFINITY) {
                if (dist[i][j] >(dist[i][k] + dist[k][j])) {
                  dist[i][j] = dist[i][k] + dist[k][j];
                  path[i][j] = k;
                }
               }
             }
           }
        }
}

Anyway, the statement else if(g.isEdge(c2, c1) == true) is redundant. Use else if(g.isEdge(c2, c1)) instead.

Hope this helps.

[Tigerdude]

The edge function is called using isEdge(toKey, fromKey) while the reachalbe function is called with isReachable(fromKey, toKey). The graph contains no negative values. I've tried a couple of different prints to check the output of the things that I'm getting, and the initial dist[][] is giving the correct values. I didn't touch the Shortest-Path part of the problem. That was written for us, so all we have to do is implement this correctly.

One interesting thing is that I'm actually getting the shortest distances printed in the dist[][] variable :rolleyes: I'm a little unsure of what you mean by point 1, but that may be it. It goes through and checks correctly, and even adds the distances correctly. The problem is coming from the numbers it puts into path[][].

For example, the 1 -> 2 edge exisits, so the reference on path[0][1] is 0. If I try 1 -> 3 where that edge doesn't exist, the path reference is path[0[2] = 1, while path[1][2] = 0. This seems correct, but when it runs the shortest path, it tries to do from 1 -> 1 and throws an exception. Another case it does is 1 -> 4, which doesn't exist. path[0][3] = 4 (which doesn't exist) and path [4][3] =0. This puts me into a loop when passed back.

And after all this, I double checked my teachers algorithm for shortest path, and have decided that he's going to pay. There's a line that goes:

while (path[initial-1][dest-1] != 0)
                        dest = path[initial-1][dest-1];

This doesn't take the fact that all the array numbers are one less than the actual vertex number. I went and made this change:

while (path[initial-1][dest-1] != 0)
                        dest = path[initial-1][dest-1] + 1;

This means that.....my floyd was fine! He wrote the wrong shortest path and did this to me :eek: I'm sorry if I wasted your time, but thanks for the help you did give me. I"ll make sure he suffers for the trouble he's caused :evil:

[AstroNox]

Dear Tigerdude, glad that you've worked it out. Well, you shouldn't hold it on your lecturer 'cause people do make mistakes. Logic error anyone? :)

Anyway, what I meant in the first point is that you are used a constant value within the int range to represent INFINITY (say 5 for instance), and so happened that the distance of the edge happens to be 5 . This would be a potential logic error and could cause major headaches later on. You could make sure that your distances will never coincide with this INFINITY value, or you can simple use a double or float ; they have a representation for infinity ( Double.POSITIVE_INFINITY or Float.POSITIVE_INFINITY ) in them.

You might want to mark this thread as solved. Thanks!