找到一个给定的源和目的地的集合之间的最短路径 [英] Find the shortest path between a given source and a set of destinations

查看:389
本文介绍了找到一个给定的源和目的地的集合之间的最短路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

您将得到一个加权连通图(20节点)与具有正权重的所有边缘。我们有在A点开始的机器人,它必须通过在点B,D和E的例子。这样做是为了发现连接所有这些4个点的最短路径。该机器人还具有有限的电池,但它可以在某些点进行充电。

You are given a weighted connected graph (20 nodes) with all edges having positive weight. We have a robot that starts at point A and it must pass at points B, D and E for example. The idea is to find the shortest path that connects all these 4 points. The robot also has a limited battery, but it can be recharged in some points.

在网上查询后,我心里有两种算法: Dijkstra的 TSP Dijkstra的将找到一个节点与所有其他节点之间的最短路径的 TSP 会发现,连接所有点的最短路径。有没有在 TSP ,只有找到最短的一组节点之间的路径的任何变种?毕竟,在 TSP 所有节点都标记必须通过。我还没有考虑在考虑电池的约束。

After researching on the internet I have two algorithms in mind: Dijkstra's and TSP. Dijkstra's will find the shortest path between a node and every other node and TSP will find the shortest path that connects all points. Is there any variant of the TSP that only finds the shortest path between a set of nodes? After all, in the TSP all nodes are labeled "must-pass". I'm still not taking in account the battery constraint.

在此先感谢!

推荐答案

您可以将您的图形降低到TSP,然后调用就可以了TSP的算法:

You can reduce your graph to a TSP and then invoke a TSP algorithm on it:

  1. 使用弗洛伊德 - 沃肖尔算法找到距离 U,V 为所有顶点对 U v
  2. 创建一个新的图,仅包含理想的顶点,并设置两个这样的顶点之间的权重 U v 由弗洛伊德 - 沃肖尔发现的距离。
  3. 运行的TSP求解所述修改的曲线图,以获得在修改图中的路径,并在修改后的图,从原始图中的最短路径切换每个边缘。
  1. Use Floyd-Warshall algorithm to find the distance u,v for ALL pairs of vertices u and v.
  2. Create a new graph, containing only the "desired" vertices, and set the weight between two such vertices u and v as the distance found by Floyd-Warshall.
  3. Run TSP Solver on the modified graph to get the path in the modified graph, and switch each edge in the modified graph with a shortest path from the original graph.

以上是最佳的,因为假定有一个较短的路径。


The above is optimal, because assume there is a shorter path.

D0=u->...D1->...->D2->...->Dk->...->t=D{k+1}

二 - > ...- D 1和D {I + 1} 至少 FloydWarshall(DI,D {重量1 + 1})弗洛伊德-沃肖尔的(正确性),因此边缘(D0,D1),(D1,D2),......,(的Dk,D- {K + 1)存在于改性图形用重量小于/等于所述给定的路径在重量

Di->...->D{i+1} has at least the weight of FloydWarshall(Di,D{i+1}) (correctness of Floyd-Warshall), and thus the edges (D0,D1),(D1,D2),...,(Dk,D{k+1) exist in the modified graph with a weight smaller/equal the weight in the given path.

因此​​,从TSP-求解的正确性,使用 D0〜> D 1 - > ...-> DK-D 1和D {K + 1} ,你至少是不如候选最优路径的路径。

Thus, from correctness of your TSP-Solver, by using D0->D1->...->Dk->D{k+1}, you get a path that is at least as good as the candidate optimal path.

这篇关于找到一个给定的源和目的地的集合之间的最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆