问Dijkstra算法特例
EN

Stack Overflow用户

提问于 2016-11-26 09:27:34

回答 1查看 79关注 0票数 0

我正在用Python实现Dijkstra最短路径算法。图是有向的和加权的。图有1070375个顶点。第一项任务是寻找顶点#100562和1070345之间的最短路径。我做到了。我对此没有异议。但是第二个任务是找到这些顶点之间的唯一路径数，它们具有相同的长度和不同的内部顶点。我的问题是，这意味着：之间的唯一路径，具有相同的长度和不同的内部顶点。从100562到1070345可以有很少的路径，或者是唯一的路径，例如，从顶点# 111700到顶点#111704。你能在简单的图表例子上展示它吗？

algorithm

unique

dijkstra

python

回答 1

Stack Overflow用户

发布于 2016-11-26 10:00:53

两个顶点之间的多条唯一最短路径的简单示例如下：

  (111700) -2-> (1117002) -2-> (1117004)
         \        /           /   
          \      /          3   
           1    3         /      
            \  /        /      
             \/       /      
           (1117001)

在这种情况下，从111700到1117004有两条最短路径。一个是长度为4的111700 -> 1117002 -> 1117004，另一个来自1117000 -> 1117001 -> 1117004，也是4长的。

但是111700 -> 1117001 -> 1117002 -> 1117004显然不是一条最短的路径，因为这条路径的长度是5(注意，如果在这个例子中，边1117001 -> 1117002的权重为1，我们将有第三条最短路径)

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/40816847

复制

相似问题

问Dijkstra算法特例
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Dijkstra算法特例EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Dijkstra算法特例
EN