所以我编写了一个算法,用于查找无向、未加权图中不同的最短路径的数量。我相信它是正确的,但我无法弄清楚运行时间是多少。非常感谢所有帮助!
shortestPaths(undirected graph G, startNode v, endNode end)
initialize all levels of nodes to -1
count = 1;
initialize queue Q = {v}
level(v) = 0
while Q is not empty
curr = pop(Q)
if( curr == end)
w = pop(Q)
while(level(w)==level(curr))
if(w == end)
count++
w=pop(Q)
return count
for all neighbors (nxt) of node curr do
if( level(nxt) == -1 )
level(nxt) = level(curr) + 1
Push(Q, nxt)
else if( level(nxt) == level(curr) + 1 )
Push(Q, nxt)
else if( level(nxt) > level(curr) + 1)
Level(nxt) = Level(curr) + 1
return count
最佳答案
算法的运行时间呈指数级增长。您可以通过不将一个顶点多次插入堆中来避免这种情况,而是通过将一个计数器与每个顶点相关联并随着到该顶点的每条新路径递增它。
尝试这样的事情:
initialize all counts of nodes to 0 // added
counts(v) = 1 // added
...
while Q is not empty
curr = pop(Q)
if( curr == end)
return counts(curr)
for all neighbors (nxt) of node curr do
if( level(nxt) == -1 )
level(nxt) = level(curr) + 1
counts(nxt) = counts(curr) // added
Push(Q, nxt)
else if( level(nxt) == level(curr) + 1 )
counts(nxt) += counts(curr) // added & removed
return 0
这与 BFS 具有相同的复杂性- O(|E|+|V|)
。
关于algorithm - 最短路径算法的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52601588/