c++ - 获取最近的路径图

Question

我有一个有向图在哪里

1 - From 
2 - To
3 - Start time (HH:mm, casted to integer) 60 => 01:00
4 - difference between endtime, always > 0;



1 2 60 120
1 2 720 125
1 2 900 120
1 3 390 90
1 3 1040 95
2 3 780 180
2 3 1260 180
2 4 240 240
2 4 300 240
2 4 1080 240
3 1 165 90
3 1 1430 90
3 2 1432 180
3 5 1431 249
4 2 1080 240
4 3 720 60

让我们忘记开始时间列，但是获得最近路径的最简单算法是什么，从 1 到 5，这意味着，通过获得最近路径，其中第四列总和较小。 .

提一下:我没有制作真正的节点，我只有关于边缘的信息，我正在像这样写在数组中

edges[ ''counter'' ] [0] = from;
edges[ ''counter'' ] [1] = to;
edges[ ''counter'' ] [2] = timeToInt(time);
edges[ ''counter'' ] [3] = timeToInt(endTime) - edges[ ''counter'' ] [2];

我听说过 Dijkstra algorithm , 但如何实现。

Answer 1

这里与你的编程语言无关，这纯粹是一个算法问题。您的一些不错的选择包括:

• Dijkstra's algorithm ，如果所有边都具有非负成本，如您的示例所示。 Dijkstra 的速度很快，而且很容易实现。有 an implementation在 Boost 和 Google 搜索中应该会出现大量的实现。
• A* ，这真是 Dijkstra 的变种。甚至更快，但启发式的，所以可以提供一个不是最好的解决方案，并且可能更难以实现。我强烈建议在实现基本的 Dijkstra 之后，在某个时候实现 A* 作为练习。再一次，A* exists in Boost .
• Bellman-Ford，如果您需要扩展到负边权重。还有 present in Boost ，只是有点困难。