algorithm - 最短路径算法的时间复杂度
问题描述
所以我写了一个算法,它在一个无向、未加权的图中找到不同最短路径的数量。我相信这是正确的,但我无法弄清楚运行时间是多少。非常感谢所有帮助!
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|)
。
推荐阅读
- mysql - 不存在给出零行
- java - 处理 multipart/form-data 请求时,srpingboot 1.3.7 中的文件始终为空
- ios - 切片字符串 Swift
- ios - 如何在 Swift 中将 ImageSliderShow pod 与 collectionView 一起使用?
- javascript - 均匀空间可见 React Native ScrollView 元素
- python - 制作程序随机掷 6 面骰子
- java - 如何从 Java rowMapper 中删除样板代码?
- html - 从直接子级的 XPath 获取文本
- python - 如何建立连接以在 python 中使用 dbpediaSpotlight?
- html - 当我在 Sublime 中保存一个 CSS 文件时,它会显示一个警报,我需要获取 Node.js