Error in FloydWarshwall algorithm

[MNadal-Yseop]

Hi,

It seems that the FloydWarshallShortestPaths algorithm could give a wrong result for PseudoGraph. Actually, it assumes there is only one edge between two node.

During path length computation process, the d matrix is initialized with the following lines :
Set edges = graph.edgeSet();
for (E edge : edges) {
V v1 = graph.getEdgeSource(edge);
V v2 = graph.getEdgeTarget(edge);

        int v_1 = vertices.indexOf(v1);
        int v_2 = vertices.indexOf(v2);

        d[v_1][v_2] = graph.getEdgeWeight(edge);
        if (!(graph instanceof DirectedGraph<?, ?>)) {
            d[v_2][v_1] = graph.getEdgeWeight(edge);
        }
    }

And no test are done to check if d[v_1][v_2] already have a value. It should be an if to check that :
Set edges = graph.edgeSet();
for (E edge : edges) {
V v1 = graph.getEdgeSource(edge);
V v2 = graph.getEdgeTarget(edge);

        int v_1 = vertices.indexOf(v1);
        int v_2 = vertices.indexOf(v2);
        if (d[v_1][v_2] > graph.getEdgeWeight(edge) {
            d[v_1][v_2] = graph.getEdgeWeight(edge);
            if (!(graph instanceof DirectedGraph<?, ?>)) {
                d[v_2][v_1] = graph.getEdgeWeight(edge);
            }
        }
    }

Sorry to don't make a real proper patch, it is my first comment on github so I'm not used to available tools ;).

Thanks for your work on JGraphT :)
M. Nadal

[jkinable]

This issue is currently being addressed in pull request #317

[jkinable]

This issue has been resolved in pull req #317. Thanks for reporting! Let us know if you encounter any other issues.