最快路径算法

Question

我需要想办法解决这个问题。我正在使用Java，但暂时不重要。我不需要任何代码，因为我必须自己这么做，我只是需要一些关于算法的建议，因为我找不到任何快速的方法来做这件事。(我的解决方案在编译时花了太长时间)

的问题是：

这里有四个城市。每条路线从一条到另一条不同(总共16条)

从城市1到城市4和从城市4到城市1是不同的(所有的路线都是单向的)，这就是为什么它们有不同的价值。

我有每条路所需的时间列表，总共是16。实际上，当程序启动时，这个列表将由用户输入，但是您可以假设我现在已经有了列表。

在我们得到所需的时间后，用户选择一个开始和结束的城市，程序必须找到旅行的最短时间。

示例：

0  18 15 8
18 0  7  3
7  16 0  19
10 14 19 0

这是一张旅行时间表。I(行)x j(列)和值显示从i到j城市的旅行时间。

当用户输入"4 2“(从城市4到城市2 )时，作为答案的输出应该是14。

但是当用户输入“2.1”时，作为答案的输出应该是13(3+10)。首先从城市2到城市4，即3小时，然后从4城市到1城市，10小时，总共13小时。

因此，选择的路线不需要是直通车，两个城市之间可以使用多少条路线，但以最快的方式使用。

这个4x4表只是4个城市的一个例子。(这也是我的全部)。该算法适用于100多个城市。在填写每个城市之间的旅行时间表之前，用户将键入城市数量。

我可能会为4个城市找到一个解决方案，但它对100个城市不起作用。我也尝试了使用java的置换方法，但是正如我所说的，编译过程太长了。但是，编译过程不需要超过4秒。

抱歉，我的问题又长又无聊，但我希望有人能给我一个有用的建议。

Answer 1

我已经想好了怎么做，所以我自己回答。我已经通过编辑我找到的这里代码来使它工作。它运行得非常快，而且完美无缺。