最短路径算法有哪些应用？

Question

图中节点之间的最短路径可以通过几种算法(Dikstra,A-star等)找到.

但是这个问题有哪些应用？(我已经知道了很多,但我想看到更多的例子).

请只提供一个申请/答案!解释应用程序,以及如何将其转换为最短路径问题.

Answer 1

最短路径算法有一个有趣的,而不是直接明显的应用,它可能经常用于处理交易资产和货物的算法交易和金融部门.

想象一下,您可以将1000美元转换为950欧元,然后将950欧元转换为1020加元,然后将其转换回1007美元:)只需将货币转换为货币即可赚钱.

这种情况称为套利机会.这可以通过任何资产和不同市场之间完成.

在这种情况下,资产之间的关系被建模为有向边加权图,并且在图中找到所谓的负循环实际上是找到这些套利机会.

您可以在此处查看更多详细信息以及很好的解释和示例:http://algs4.cs.princeton.edu/44sp/

Answer 2

鉴于许多高速公路连接城市,找到从纽约到芝加哥的最短路径.

高速公路的交通和长度是路径权重.

Answer 3

最短路径算法可用于解决字梯拼图.

例如,通过一次更改一个字母将"cat"改为单词"dog" - "cat","bat","bag","bog","dog"

Answer 4

给定一个计算机网络（例如，对等应用程序），找到从机器 A 到机器 B 的最短路径。