All Pairs Shortest Paths

Finds the shortest path between all pairs of nodes in mixed graph of n nodes with any given edge lengths.

    public static void allPairsShortestPaths(int n, int dist[][], int big,
                                             int startnode, int endnode,
                                             int path[]) {
        int i, j, k, d, num, node;
        int next[][] = new int[n + 1][n + 1];
        int order[] = new int[n + 1];

        // compute the shortest path distance matrix
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                next[i][j] = i;
            }
        }

        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (dist[j][i] < big) {
                    for (k = 1; k <= n; k++) {
                        if (dist[i][k] < big) {
                            d = dist[j][i] + dist[i][k];

                            if (d < dist[j][k]) {
                                dist[j][k] = d;
                                next[j][k] = next[i][k];
                            }
                        }
                    }
                }
            }
        }

        // find the shortest path from startnode to endnode
        if (startnode == 0) {
            return;
        }

        j = endnode;
        num = 1;
        order[num] = endnode;

        while (true) {
            node = next[startnode][j];

            num++;

            order[num] = node;

            if (node == startnode) {
                break;
            }

            j = node;
        }

        for (i = 1; i <= num; i++) {
            path[i] = order[num - i + 1];
        }

        path[0] = num;
    }