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\$
3
  • \$\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, 2011 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, 2011 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, 2011 at 22:27

1 Answer 1

Reset to default
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\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .