Shortest-path algorithms which use a space-time tradeoff?

Posted by Chris Mounce on Stack Overflow See other posts from Stack Overflow or by Chris Mounce
Published on 2010-04-27T20:40:51Z Indexed on 2010/04/27 20:43 UTC
Read the original article Hit count: 372

Filed under:

tradeoff

|

shortest-path

|

algorithms

I need to find shortest paths in an unweighted, undirected graph.

There are algorithms which can find a shortest path between two nodes, but this can take time. There are also algorithms for computing shortest paths for all pairs of nodes in the graph, but storing such a lookup table would take lots of disk space.

What I'm wondering: Is there an algorithm which offers a space-time tradeoff that's somewhere between these two extremes? In other words, is there a way to speed up a shortest-path search, while using less disk space than would be occupied by an all-pairs shortest-path table?

I know there are ways to efficiently store lookup tables for this problem, and I already have a couple of ideas for speeding up shortest-path searches using precomputed data. But I don't want to reinvent the wheel if there's already some established algorithm that solves this problem.

© Stack Overflow or respective owner

Related posts about tradeoff

Simplicity-efficiency tradeoff

as seen on Programmers - Search for 'Programmers'
The CTO called to inform me of a new project and in the process told me that my code is weird. He explained that my colleagues find it difficult to understand due to the overly complex, often new concepts and technologies used, which they are not familiar with. He asked me to maintain a simple code… >>> More
Simplicity-effecincy tradeoff

as seen on Programmers - Search for 'Programmers'
The CTO called to inform me of a new project and in the process told me that my code is weird. He explained that my colleagues find it difficult to understand due to the overly complex, often new concepts and technologies used, which they are not familiar with. He asked me to maintain a simple code… >>> More
Shortest-path algorithms which use a space-time tradeoff?

as seen on Stack Overflow - Search for 'Stack Overflow'
I need to find shortest paths in an unweighted, undirected graph. There are algorithms which can find a shortest path between two nodes, but this can take time. There are also algorithms for computing shortest paths for all pairs of nodes in the graph, but storing such a lookup table would take lots… >>> More
Why Android for enterprise applications?

as seen on Stack Overflow - Search for 'Stack Overflow'
Recently one of our clients is considering the posibility of picking up an old WinMobile 5.0 project. Several features are to be added to the point it will be a major version update. The client is worried about the mobile market, and thinks there's a chance all the effort put in this development… >>> More
Technical differences between square and hexagon for a grid?

as seen on Game Development - Search for 'Game Development'
I'm developing a 2D city-building game and trying to decide on the type of grid. There will be vehicles, so the unit movement is important too. I know there are visual differences for using Squares or Hexagons, what I want know is: What are the issues for programming each type of grid regarding… >>> More

Related posts about shortest-path

Algorithm shortest path between all points

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, suppose I have 10 points. I know the distance between each point. I need to find the shortest possible route passing trough all points. I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and the all give me the shortest path between start and end, but they don't make a route… >>> More
Shortest-path algorithms which use a space-time tradeoff?

as seen on Stack Overflow - Search for 'Stack Overflow'
I need to find shortest paths in an unweighted, undirected graph. There are algorithms which can find a shortest path between two nodes, but this can take time. There are also algorithms for computing shortest paths for all pairs of nodes in the graph, but storing such a lookup table would take lots… >>> More
C# - Shortest path map finding

as seen on Stack Overflow - Search for 'Stack Overflow'
I try to write a simple program in C#, it's like map finding . I've a picture of city / or district ( it's const ) and I'll add a database to this program to store variables, points . I use floyd to find the shortest path and I'll draw the path in the image ( by coordinates I think ) . This is the… >>> More
search all paths and the shortest path for a graph - Prolog

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi , I have a problem in my code with turbo prolog wich search all paths and the shortest path for a graph between 2 nodes the problem that i have is to test if the node is on the list or not exactly in the clause of member and this is my code : /* 1 ---- b ---- 3 … >>> More
Dijstra shortest path algorithm with edge cost.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I have a directed, positive weighted graph. Each edge have a cost of use. I have only A money, i want to calculate shortest paths with dijkstra algorithm, but sum of edges costs on route must be less or equal to A. I want to do this with most smallest Dijstra modification (if I can do it… >>> More