# All Pairs Shortest Paths in Weighted Undirected Graph

I'm currently working on path-finding for my game and need help with finding an efficient algorithm to calculating the all-pairs shortest paths in a weighted undirected graph (each vertex in the graph represents a way-point on my map, and each edge represents the distance between pairs of way-points).

I have considered using Floyd's Algorithm due to its simplicity and relative memory efficiency, but Floyd was designed for a directed graph, whereas my graph is undirected. This means that Floyd's algorithm is rather more expensive than required given that I know that the shortest path from vertex A to vertex B is always identical to the shortest path from B to A.

Can Floyd's algorithm be optimized to deal with this duplication? Or is there an alternative algorithm fast/space efficient algorithm that I could use to solve the same problem?

• I'm not sure this belongs on Game Dev... this is a programming theory problem, and just because you're using it in a game doesn't mean you need to ask it here. Sep 14 '11 at 21:30
• @Dan: There are a variety of similar questions here already... but I'd be happy to see mine closed / migrated if it is in the wrong place. Sep 14 '11 at 21:49
• Sorry, I didn't mean to say it's off topic here, I just was suggesting that another stack may get you better responses. Sep 14 '11 at 22:27

Sure. In the implementation in Wikipedia, change the inner loop to for j := i+1 to n, and replace all path[X][Y] with X < Y ? path[X][Y] : path[Y][X].