Python - 大规模的Dijkstra算法

Question

我有一个庞大的网络，大约有400个节点，而我正在尝试做的是计算您可以在网络上制作的每条可能路线。这意味着，节点遍历和从节点1的路径的总权重到节点2，节点1〜节点3到节点1到节点400

然后，从节点2到节点3，节点2到节点4可达节点2到节点400

（仅供参考，我有蟒蛇的认识非常有限，一天一天，我用HTML/CSS工作）

我一直在使用这个代码，我发现： http://bytes.com/topic/python/insights/877227-dijkstras-algorithm-finding-shortest-route

但是，由于我的网络规模庞大，计算从任何节点到任何节点的每种可能方式都需要非常长的时间我。

从我所了解的链接算法中，它依次从起始节点访问每个节点，并给它一个值，这是从一开始就到达该节点所需的权重（我想它也会记录到达每个特定节点所需的路线？）。如果发现到达该节点的路由较短，则会覆盖之前的节点。一旦到达目的地，它将停止并返回结果。

我想，如果脚本可以稍微编辑一下，是否可以代替在特定目的地停留，只需像往常一样访问所有节点，并打印出最短路径和加权的报告？这样，算法只需要运行总共400次，每次可能的起始位置一次。

感谢您的任何建议，你可以给我，我希望这是明确的！

Answer 1

您可以使用Python图表模块NetworkX，该模块具有适用于所有配对最短路径（weighted和unweighted）的方法。而且他们在这种意义上进行了优化，即他们使用最有名的算法来处理这些任务。

Answer 2

你所建议的调整将简单地改变其排序可能路线的方法，仅此而已。你需要的是通过使用假设来彻底改变遍历，而且djikstra在大规模实际上并不是那么高效。