使用Dijkstra检测多个最短路径

本文介绍了使用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 ) ); } ...