2
$\begingroup$

I am referring to the algorithm from the Wikipedia page on the Floyd–Warshall algorithm.

In case of undirected graphs should I change the assignment statement inside the if condition to

dist[i][j] = dist[j][i] = dist[i][k] + dist[k][j]

or they are equivalent?

$\endgroup$
  • 1
    $\begingroup$ What do you think? $\endgroup$ – Raphael Jun 2 '14 at 23:50
  • 1
    $\begingroup$ I thought that they are equivalent. $\endgroup$ – aghost Jun 3 '14 at 4:15
  • 1
    $\begingroup$ "They"? Hint: Can you ever have dist[i][j] != dist[j][i] in an undirected graph? $\endgroup$ – Raphael Jun 3 '14 at 6:30
  • $\begingroup$ You can save slightly less then half of memory (strictly saying (n * (n - 1)) / 2) for undirected graph by trade-off with slightly complicated indexing (and, therefore, runtime). $\endgroup$ – Tomilov Anatoliy Jan 9 '17 at 12:35
5
$\begingroup$

Every undirected graph can be represented as directed graph by replacing every edge $(i,j)$ with 2 edges $(i,j); (j,i)$. And if you're running Floyd–Warshall algorithm on such directed graph - it would work correctly, as always.

$\endgroup$
  • $\begingroup$ It does not work correctly if the undirected graph has a negative edge. $\endgroup$ – xskxzr Mar 23 '19 at 15:59
1
$\begingroup$

Actually this algorithm is so amazing that it works for both directed and undirected graph.

Only one thing you should keep in mind while storing distances at (i,j) you should do the same for (j,i).

graph(i,j) = graph(j,i) = distance

Rest algorithm will work fine and you only need to do:

dist[i][j] = dist[i][k] + dist[k][j]

$\endgroup$
  • 2
    $\begingroup$ Not really so amazing -- an undirected graph is just a special case of a directed graph in which the edge relation is symmetric. $\endgroup$ – David Richerby Jun 22 '16 at 10:00
0
$\begingroup$

I think for undirected graph the Floyd-Warshall algorithm can be optimized. The speedup should be 2.

            for(INTTYPE k = 0; k < num_nodes; k++) {
                for(INTTYPE i = 0; i < num_nodes; i++) {
                    INTTYPE distki = (k<i)?dist[k][i]:dist[i][k];
                    if(k == i || distki == INF) {
                        continue;
                    }

                    for(INTTYPE j = i+1; j < num_nodes; j++) {
                        INTTYPE distkj = (k<j)?dist[k][j]:dist[j][k];
                        if(k == j || i == j || distkj == INF) {
                            continue;
                        }
                        WEIGHTTYPE via = distki + distkj;
                        if(via < dist[i][j]) {
                            dist[i][j] = via;
                            prev[i][j] = k;
                        }
                    }
                }
            } 

The optimization comes in the inner-most loop(for(INTTYPE j = i+1; j < num_nodes; j++){ }). It only calculates one half of the matrix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.