shortest path for large graph
Ok im trying to create a shortest path table(s) for a large graph, around 100000 nodes, yes, 100000. Now if i use Dijkstras algorithm for 100k nodes its gonna take up 78 GIGABYTES of memory, which for obvious reasons is not possible. Is there another good way to get this done in less space? The reason Im doing is because of speed issues, eventually i want to run a simulation where it will be crucial for this to be precomputed.
Any, yes ANY ideas will be greatly appreciated...
Erik
[504 byte] By [
hochia] at [2007-10-2 6:32:39]
To rephrase, what you have is called a 'sparse matrix'. Most of the nodes do NOT connect to each other. It is a vast wast of space to store a value for each and every combination of nodes. Only store values when the nodes are connected.
Here is a simple implementation of an unbounded sparse matrix I use for a matrix indexed by integers.
You could optimise even further (assuming the edge values are bidirectional - i.e. the edge value is the same from ID1 to ID2 as from ID2 to ID1) by only storing the edge values for the lower node ID and swapping the row and column when row < column.
import java.util.*;
/**
* Implements an infinate 2 dimensional martix or array. All values of the
* matrix are assumed to be null unless a value for a cell is specified using the
* set method. Memory is dynamically allocated as the data in the matrix grows.
*
* @author$Author: kellymt $
* @version$Revision: 1.1 $ $Date: 2004/07/09 12:25:39EDT $
*/
public class UnboundedSparseMatrix
{
/**
* The matrix is implemented as a HashMap of HashMaps. The first level
* represents the 'row'. If a cell has been set in a row,
*pMatrixContents.get( new Integer( row ) )
* will return a HashMap of the contents of that row. Likewise, the value of
* each cell in that row can be determined by the call
*pRow.get( new Integer( col ) )
*/
protected HashMap pMatrixContents;
/**
* Creates a new instance of an SparseMatrix.
*/
public UnboundedSparseMatrix()
{
pMatrixContents = new HashMap();
}
/**
* Get the value of the specified cell in the matrix.
*
* @param rowNum the row of the cell whose value is being requested.
* @param colNum the column of the cell whose value is being requested.
* @return the value of this cell or null if none ever specified.
*/
public Object get( int rowNum, int colNum )
{
HashMap pRowSettings =
(HashMap)pMatrixContents.get( new Integer( rowNum ) );
if ( pRowSettings == null ) return null;
return pRowSettings.get( new Integer( colNum ) );
}
/**
* Set the value of the specified cell in a matrix.
*
* @param rowNum the row of the cell whose value is being set.
* @param colNum the column of the cell whose value is being set.
* @param pValue set the cell to this value
*/
public void set( int rowNum, int colNum, Object pValue )
{
HashMap pRowSettings =
(HashMap)pMatrixContents.get( new Integer( rowNum ) );
if ( pRowSettings == null )
{
pRowSettings = new HashMap();
pMatrixContents.put( new Integer( rowNum ), pRowSettings );
}
pRowSettings.put( new Integer( colNum ), pValue );
}
/**
* Removes all values from the matrix.
*/
public void clear()
{
pMatrixContents.clear();
}
}
