HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Floyd–Warshall algorithm on undirected graph

Submitted by: @import:stackexchange-cs··
0
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 if condition to

dist[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.