可以通过多种算法（Dikstra、A-star 等）找到图中节点之间的最短路径。
但是这个问题有什么应用呢？（我已经知道很多了，但我想看到更多的例子）。
请只提供一份申请/答案！解释应用程序，以及如何将其转换为最短路径问题。
问问题
28239 次
11 回答
9
最短路径算法有一个有趣的但不是直接显而易见的应用，它可能经常用于处理交易资产和商品的算法交易和金融领域。
想象一下，您可以将 1000 美元转换为 950 欧元，然后将 950 欧元转换为 1020 加元，然后再转换回 1007 美元 :) 只需从货币转换为货币，您就可以赚钱。
这种情况称为套利机会。这可以在任何资产和不同市场之间完成。
在这种情况下，资产之间的关系被建模为有向边加权图，在图中找到所谓的负循环实际上就是找到这些套利机会。
你可以在这里看到更多详细的解释和例子：http: //algs4.cs.princeton.edu/44sp/
于 2013-04-05T08:50:28.557 回答
6
给定许多有高速公路连接它们的城市，找到从纽约到芝加哥的最短路径。
高速公路的交通量和长度是路径权重。
于 2010-12-10T18:32:15.920 回答
5
最短路径算法可用于解决字梯谜题。
例如，通过一次更改一个字母来将单词“cat”变成单词“dog”——“cat”、“bat”、“bag”、“bog”、“dog”
于 2012-05-06T17:12:03.213 回答
4
最短路径问题构成了一整类优化问题的基础，可以通过称为列生成的技术来解决。示例包括车辆路线问题、可生存网络设计问题等。在这样的问题中有一个主问题（通常是线性程序），其中每一列代表一条路径（将车辆路径问题中的路径视为车辆可以采取的一条候选路线，将网络设计问题中的路径视为商品的可能路线可以在源和目的地之间发送）。主问题反复解决。每次，使用解决方案的度量，都会解决一个单独的问题（称为列生成子问题）。这个问题原来是一个最短路径问题（通常带有边约束或负弧长，呈现问题 NP-Hard）。如果获得了新的有用路径，则将其添加到原始主问题中，该主问题现在在更大的路径子集上重新解决，从而导致越来越好的（通常成本更低）的解决方案。
于 2010-12-11T14:16:23.770 回答
2
我可以看到它可能正在使用的一个例子是预先设定的点设备，这些设备需要使用特定数量的电池电量或燃料通过某些点。
在军队中，我们有一些小型无人驾驶飞行器/设备，它们有一些需要侦察的预设点，并且由于它必须飞行很远的距离，在这样的小型设备上尝试通过它来控制它太昂贵了卫星和无线电控制在到达最远点之前会恶化。这就是算法发挥作用的地方。
只需设置某个点，您希望该事物可以侦察并释放它。让它找到覆盖所有点的最短路径。它不需要主要工具，因此更实惠且便携。
于 2010-12-10T18:37:21.627 回答
2
给定一个计算机网络（例如，对等应用程序），找到从机器 A 到机器 B 的最短路径。
于 2010-12-10T18:31:18.463 回答
2
在电子游戏中，这些算法经常被用来寻找地图上两点之间的最短路径。在这种情况下，“寻路”可以被人工智能用来绘制路线，或者被游戏引擎用来帮助用户绘制路线。
于 2010-12-10T18:32:34.613 回答
2
社交网络...寻找两个人之间的最短路径（分离度）
于 2010-12-10T19:28:21.543 回答
2
尚未提及的一个很酷的应用是边缘检测和分割。请参阅使用智能剪刀进行交互式分割。您可能在 Photoshop 中将其称为“磁性套索”
于 2021-08-27T20:10:29.987 回答
1
于 2010-12-10T18:43:48.897 回答
1
SNA（社交网络分析）中经常使用最短路径来计算介数中心性。通常具有最强联系的人倾向于通过最短路径进行交流。在图中了解人（节点）之间的最短路径可以让您了解隐藏的强联系。只需计算一些指标，您就可以在图表中发现许多有趣的东西。
于 2014-02-08T03:19:36.910 回答