正如标题所说，我正在尝试实现一种算法，找出给定图中所有节点对之间的距离。但还有更多：（可能对您有帮助的事情）
|E| <= 4*|V|我知道所有对的 Johnson 算法、Floyd-Warshal和Dijkstra。但是当图有权重时，这些算法很好。
我想知道是否有更好的算法适合我的情况，因为这些算法适用于加权图。
谢谢！
有改进的空间，因为在未加权图中，您获得了一个附加属性，该属性不适用于加权图，即：
对于直接连接 A 到 C 的任何边，您肯定知道没有通过第三个节点 B 的更短路径。
考虑到这一点，您应该能够简化 Dijkstra 算法：您可能知道，它适用于三组节点：
当沿着e从A(1.) 到C(3.) 的边时，原始 Dijkstra 会将节点C从 (3.) 移动到 (2.)。由于上述属性适用于所有图表，因此您可以将其直接添加到集合 (1.) 中，这样效率更高。
这是基本的观察：上面概述的过程基本上是一个 BFS（广度优先搜索），即您可以找到从某个固定节点v到 中的任何其他节点的距离O(|V| + |E|)。
您在原始问题中没有提到该图基本上是一个带有一些孔的网格。这是一个更严格的要求，我相信你可以利用它。快速搜索“网格图最短路径”会产生这篇论文O(sqrt(n))，它在最好的情况下承诺。由于您指定的问题结构良好，我几乎可以肯定还有几篇您可能想要查看的论文。
从每个节点运行广度优先搜索。总时间：O(|V| |E|) = O(|V| 2 )，这是最优的。
我建议你试试 networkx，它似乎在 1000 个节点上运行良好。
以下链接包含未加权图的最短路径算法：
http://networkx.lanl.gov/reference/algorithms.shortest_paths.html
这是一个有 10 个节点的示例：
from random import random
import networkx as nx
G=nx.DiGraph()
N=10
#make a random graph
for i in range(N):
for j in range(i):
if 4*random()<1:
G.add_edge(i,j)
print G.adj
print nx.all_pairs_shortest_path(G)
print nx.all_pairs_shortest_path_length(G)
#output:
#Graph ADJ={0: {}, 1: {}, 2: {}, 3: {0: {}, 2: {}}, 4: {}, 5: {0: {}, 3: {}, 4: {}}, 6: {0: {}, 1: {}, 4: {}}, 7: {2: {}, 4: {}, 6: {}}, 8: {1: {}}, 9: {2: {}, 5: {}}}
#PAIRS={0: {0: [0]}, 1: {1: [1]}, 2: {2: [2]}, 3: {0: [3, 0], 2: [3, 2], 3: [3]}, 4: {4: [4]}, 5: {0: [5, 0], 2: [5, 3, 2], 3: [5, 3], 4: [5, 4], 5: [5]}, 6: {0: [6, 0], 1: [6, 1], 4: [6, 4], 6: [6]}, 7: {0: [7, 6, 0], 1: [7, 6, 1], 2: [7, 2], 4: [7, 4], 6: [7, 6], 7: [7]}, 8: {8: [8], 1: [8, 1]}, 9: {0: [9, 5, 0], 2: [9, 2], 3: [9, 5, 3], 4: [9, 5, 4], 5: [9, 5], 9: [9]}}
#LENGTHS={0: {0: 0}, 1: {1: 0}, 2: {2: 0}, 3: {0: 1, 2: 1, 3: 0}, 4: {4: 0}, 5: {0: 1, 2: 2, 3: 1, 4: 1, 5: 0}, 6: {0: 1, 1: 1, 4: 1, 6: 0}, 7: {0: 2, 1: 2, 2: 1, 4: 1, 6: 1, 7: 0}, 8: {8: 0, 1: 1}, 9: {0: 2, 2: 1, 3: 2, 4: 2, 5: 1, 9: 0}}
如果所有边缘都未加权，我不知道如何测量距离，但您想查看 Edmond 的 Blossom V 算法。您想查看http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs。这是类似的内容：http ://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html 。
我建议您参考以下论文：Tadao Takaoka 的“所有对最短路径问题的次立方成本算法”。对于具有单位权重的图（实际上最大边权重 = O(n ^ 0.624)），可以使用具有亚三次复杂度的顺序算法。
我假设图表是动态的；否则，没有理由不使用 Floyd-Warshall 在这么小的图上预先计算所有对的距离；）
假设您有一个点 (x, y) 网格，其中 0 <= x <= n, 0 <= y <= n。删除边 E: (i, j) <-> (i+1, j) 后，您将行 j 划分为集合 A = { (0, j), ..., (i, j) }, B = { (i+1, j), ..., (n, j) } 使得 A 中的点 a，B 中的 b被迫绕 E 路由 - 所以您只需要重新计算所有对 (a, b) 的距离在（A，B）中。
然后，也许您可以预先计算 Floyd-Warshall，然后使用类似的方法将每次图形修改的重新计算减少到 O(n^2)（左右）......
Warshall 算法怎么样，具有以下非常简单的实现：
def warshall(graph):
n = graph.numNodes+1
W = [ [graph.w(i,j) for j in graph.V()] for i in graph.V() ]
for k in range(1,n):
for i in range(1,n):
for j in range(1,n):
W[i][j] = min( W[i][j] , W[i][k]+W[k][j] )
return W
在哪里
V()产生图的所有顶点w(i,j)产生边缘 (i,j) - 在你的情况下都是 1 或 0numNodes产生图的节点数。复杂度是，但是 O(n^3)
def from_vertex(v, E):
active = [v]
step = 0
result = {v:0}
while active:
step += 1
new_active = []
for x in active:
for nh in E[x]:
if nh not in result:
new_active.append(nh)
result[nh] = step + 1
active = new_active
return result
基本上，您从每个顶点进行泛洪填充，结果得到任何其他可到达顶点与该顶点的最小距离。
在 Python 图形项目中：
http://code.google.com/p/python-graph/
你可以找到我的支持提示启发式的 A* 算法的实现。这特别适用于二维避障，因为提示算法不需要比毕通格拉斯定理更多。
我认为这会做你需要的一切。如果您不喜欢该项目使用的图形抽象，您可以重用该算法。它以非常通用的方式编写。
在快速浏览了算法设计手册之后，这是 Skiena 必须说的（来自第 15.4 章 - 最短路径）。不出所料，它得出的结论与你们许多人已经提供的相同，但也提供了一些其他见解
寻找最短路径的主要算法是 Djikstra 算法......
您的图表是加权的还是未加权的？如果您的图未加权，则从源顶点开始的简单广度优先搜索将在线性时间内找到到所有其他顶点的最短路径...
他继续提到您可能感兴趣的其他情况（例如，如果输入是一组几何障碍怎么办？您需要所有点对之间的最短路径吗？）但在这些情况下，他也得出与您相同的结论有：Djikstra 算法或 Floyd-Warshall 算法。
根据您的使用情况，您可能还想研究处理可达性的传递闭包，并使用类似的算法。