patternMinor
Floyd–Warshall algorithm on undirected graph
Viewed 0 times
floydgraphwarshallalgorithmundirected
Problem
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
or they are equivalent?
In case of undirected graphs should I change the assignment statement inside the
if condition todist[i][j] = dist[j][i] = dist[i][k] + dist[k][j]or they are equivalent?
Solution
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.
Context
StackExchange Computer Science Q#26344, answer score: 6
Revisions (0)
No revisions yet.