在 O(V + E) 时间内在加权无向图中找到从源到目标的最短路径
Find the shortest path from source to target in a weighted-undirected graph in O(V + E) time
我的任务是设计一种算法，在 O(V + E) 时间内找到具有 V 个节点和 E 条边的加权无向图中的最短路径。图权重均为正整数，没有大于15的权重。
我相信我可以使用 Dijkstra 算法找到从源节点到目标节点的最短路径，但我认为它不满足运行时约束。
了解 BFS 和 DFS 的运行时，我认为对这些算法进行某种修改将使我达到 O(V + E)，但我不确定该朝哪个方向或如何前进我可以利用边缘上的 <= 15 权重约束。
感谢任何帮助。
你可以使用 Dijkstra 算法，但是你必须小心处理优先级队列。
由于所有的权重都是1到15的整数，所以队列中同一时刻只能有16个不同的优先级。您可以使用此事实在恒定时间内实现所有优先级队列操作。这会将算法的复杂度从 O(|V| + |E| log |V|) 更改为 O(|V| + |E|)
有很多方法可以建立优先队列。基本上，您将条目划分为具有相同优先级的条目列表，然后您只需对 16 个列表进行优先级排序。将这 16 个列表放在一个循环数组中是合理的。
您正在寻找的算法称为 Dial 算法，因为它也适用于包含循环的图形。它的复杂度是O(E + WV)。如果 W>>V，您可以将每个 W 的一个桶替换为权重 1, 2-3, 4-7, 8-15 etc 的桶。
这是对 Dijkstra 的优化，它使用了这样一个事实，即给定权重范围，您可以用桶替换斐波那契堆，这将减少 find_node 操作从 O(logn)至 O(1).
详细的算法在 GeeksForGeeks and Wikipedia 中有详细描述。
您还应该对 Cormen 算法导论中的有向无环图最短路径感兴趣。 655 或 GeeksForGeeks
我的任务是设计一种算法，在 O(V + E) 时间内找到具有 V 个节点和 E 条边的加权无向图中的最短路径。图权重均为正整数，没有大于15的权重。
我相信我可以使用 Dijkstra 算法找到从源节点到目标节点的最短路径，但我认为它不满足运行时约束。
了解 BFS 和 DFS 的运行时，我认为对这些算法进行某种修改将使我达到 O(V + E)，但我不确定该朝哪个方向或如何前进我可以利用边缘上的 <= 15 权重约束。
感谢任何帮助。
你可以使用 Dijkstra 算法，但是你必须小心处理优先级队列。
由于所有的权重都是1到15的整数，所以队列中同一时刻只能有16个不同的优先级。您可以使用此事实在恒定时间内实现所有优先级队列操作。这会将算法的复杂度从 O(|V| + |E| log |V|) 更改为 O(|V| + |E|)
有很多方法可以建立优先队列。基本上，您将条目划分为具有相同优先级的条目列表，然后您只需对 16 个列表进行优先级排序。将这 16 个列表放在一个循环数组中是合理的。
您正在寻找的算法称为 Dial 算法，因为它也适用于包含循环的图形。它的复杂度是O(E + WV)。如果 W>>V，您可以将每个 W 的一个桶替换为权重 1, 2-3, 4-7, 8-15 etc 的桶。
这是对 Dijkstra 的优化，它使用了这样一个事实，即给定权重范围，您可以用桶替换斐波那契堆，这将减少 find_node 操作从 O(logn)至 O(1).
详细的算法在 GeeksForGeeks and Wikipedia 中有详细描述。
您还应该对 Cormen 算法导论中的有向无环图最短路径感兴趣。 655 或 GeeksForGeeks