戴克斯特拉算法
{{Infobox algorithm |class=搜索算法 |image=Dijkstra Animation.gif |caption = 戴克斯特拉算法运行演示（找到A，B之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。 |data=图 堆/优先队列（算法优化） |best-time= |average-time= |SpaceComp=O(|E|+|V|)…
标签：#圖算法
共 3 篇文章
Tarjan算法
Tarjan算法（以發現者Robert Tarjan命名）是一個在圖中尋找強連通分量的算法。雖然發表時間更早，它仍可以被視為Kosaraju算法的一個改進。它的效率跟差不多。 概述 此算法以一個有向圖作為輸入，並按照所在的強連通分量給出其頂點集的一個劃分。圖中的每個節點只在一個強連通分量中出現，即使是在有些節點單獨構成一個強連通分量的情況下（比如圖中出現了樹形結構或孤立節點）。 算法的基本思想如下：任選一節點開始進行深度優先搜索（若深度…
最短路徑樹
最短路径树（shortest-path tree），是一种使用最短路径算法生成的数据结构树。 定义 考虑一个连通无向图G，一个以顶点v为根节点的最短路径树T是图G满足下列条件的生成树——树T中从根节点v到其它顶点u的路径距离，在图G中是从v到u的最短路径距离。 在一个所有最短路径都明确（例如没有负长度的环）的连通图中，我们可以使用如下算法构造最短路径树： 使用戴克斯特拉算法或贝尔曼-福特算法计算图 G 中从根节点 v 到 顶点 u 的最…