Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  dlras2 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. –  Kramii 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. –  dlras2 Sep 14 '11 at 22:27
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
Exactly what I needed! Thanks. –  Kramii Sep 15 '11 at 9:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.