2
\$\begingroup\$

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?

| improve this question | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – dlras2 Sep 14 '11 at 21:30
  • \$\begingroup\$ @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. \$\endgroup\$ – Kramii Sep 14 '11 at 21:49
  • \$\begingroup\$ Sorry, I didn't mean to say it's off topic here, I just was suggesting that another stack may get you better responses. \$\endgroup\$ – dlras2 Sep 14 '11 at 22:27
3
\$\begingroup\$

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].

| improve this answer | |
\$\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.