Python - 大规模的Dijkstra算法
我有一个很大的网络，大约有400个节点。我想做的事情是计算在这个网络上可以走的每一条可能的路线。这意味着我要从节点1到节点2、节点3，一直到节点400，计算经过的节点和这条路线的总权重。
然后再从节点2到节点3、节点4，一直到节点400。
顺便说一下，我对python的了解非常有限，平时主要使用HTML和CSS。
我发现了一段代码在用：http://bytes.com/topic/python/insights/877227-dijkstras-algorithm-finding-shortest-route
这段代码很好，但是由于我的网络规模太大，从任何一个节点到任何一个节点计算所有可能的路径需要非常非常长的时间。
根据我对我链接的算法的理解，它会依次访问每个节点，从起始节点开始，并给每个节点一个值，这个值是从起始节点到达该节点所需的权重（我想它也会记录到达每个特定节点所需的路径？）。如果它找到了一条更短的路径到达那个节点，它就会覆盖之前的值。一旦到达目标节点，它就停止并返回结果。
我在想，如果稍微修改一下这个脚本，能不能让它在不停止于特定目标的情况下，像往常一样访问所有节点，并打印出到每个节点的最短路径和权重的报告？这样的话，算法只需要运行400次，每次从一个不同的起始位置开始。
感谢你能提供的任何建议，希望我说得清楚！
2 个回答
你提到的这个调整只是改变了可能路径的排序方式，没别的意思。你需要做的是大幅度改变遍历的方法，同时，Dijkstra算法在大规模数据上其实效率并不高。
你可以使用Python的图形模块 NetworkX，这个模块有一些方法可以帮助你找到所有点之间的最短路径。它提供了两种方式：一种是考虑权重的路径（weighted），另一种是不考虑权重的路径（unweighted）。而且这些方法都是经过优化的，意味着它们使用了目前已知的最佳算法来完成这些任务。