World's most popular travel blog for travel bloggers.

Floyd–Warshall algorithm on undirected graph

, , No Comments
Problem Detail: 

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?

Asked By : Anirban Ghosh

Answered By : Ralor

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26344

0 comments:

Post a Comment

Let us know your responses and feedback