java - 使用 Dijkstra 检测多条最短路径
问题描述
给定一个加权有向图,如何修改 Dijkstra 算法以测试给定节点对之间是否存在多个最低成本路径?
我目前的算法如下:(归功于 Weiss)
/**
* Single-source weighted shortest-path algorithm. (Dijkstra)
* using priority queues based on the binary heap
*/
public void dijkstra( String startName )
{
PriorityQueue<Path> pq = new PriorityQueue<Path>( );
Vertex start = vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
clearAll( );
pq.add( new Path( start, 0 ) ); start.dist = 0;
int nodesSeen = 0;
while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )
{
Path vrec = pq.remove( );
Vertex v = vrec.dest;
if( v.scratch != 0 ) // already processed v
continue;
v.scratch = 1;
nodesSeen++;
for( Edge e : v.adj )
{
Vertex w = e.dest;
double cvw = e.cost;
if( cvw < 0 )
throw new GraphException( "Graph has negative edges" );
if( w.dist > v.dist + cvw )
{
w.dist = v.dist +cvw;
w.prev = v;
pq.add( new Path( w, w.dist ) );
}
}
}
}
解决方案
替换 field prev
,用集合链接到上一个顶点prevs
,并稍微更改代码:
...
if( w.dist >= v.dist + cvw ) {
if ( w.dist > v.dist + cvw ) {
w.dist = v.dist +cvw;
w.prevs.clear();
}
w.prevs.add(v);
pq.add( new Path( w, w.dist ) );
}
...