使用Dijkstra检测多个最短路径 [英] Using Dijkstra to detect multiple shortest paths
本文介绍了使用Dijkstra检测多个最短路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
给定一个加权有向图,如何修改Dijkstra算法以测试给定节点对之间是否存在多个最低成本的路径?
Given a weighted directed graph, how can the Dijkstra algorithm be modified to test for the presence of multiple lowest-cost paths between a given pair of nodes?
我的当前算法如下:(贷给魏斯)
My current algorithm is as follows: (credit to 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 ) );
}
}
}
}
推荐答案
替换字段 prev
,链接到具有集合 prevs
的先前顶点,并稍微更改代码:
Replace field prev
, the link to previous vertex with a collection prevs
, and change the code slightly:
...
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 ) );
}
...
这篇关于使用Dijkstra检测多个最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文