Search code examples
algorithmgraph-algorithmdata-representationundirected-graph

Which algorithm+representation should I use for finding minimum path distance in a huge sparse undirected graph?

I need to find the minimum distance between two nodes in a undirected graph, here are some details

  • The graph is undirected and huge(no of nodes is in order of 100,000)
  • The graph is sparse, no of edges is less than no of nodes
  • I am not interested in the actual path, just the distance.

What representation and algorithm should I use for a) Space efficiency b)time efficiency?

EDIT: If it matters,

  • The wieghts are all non zero positive integers.
  • No node connects to itself.
  • Only single edge between two adjacent nodes
Solution

  • It depends on the weights of the edges. If they are non-negative - Dijkstra suits you. If your graph is planar, you can use A*.

    If you have negative weights, you have to use Bellman-Ford.