`
java-mans
  • 浏览: 11710521 次
文章分类
社区版块
存档分类
最新评论

单源最短路径

 
阅读更多

单源最短路径问题就是给定你一个有向图G = (V, E),找出一个点到另一个点的最短路径。

这里用Dijkstra's algorithm来找出最短路径。

这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,原点 s 的路径长度值被赋为 0 (d[s]= 0),同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点vsd[v]= ∞)。当算法结束时,d[v]中储存的便是从sv的最短路径,或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展:如果存在一条从uv的边,那么从sv的最短路径可以通过将边(u,v)添加到尾部来拓展一条从 s 到 u 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的 d[v] 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候每条边(u,v)都只被拓展一次。

算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 d[v] 的值已经是最短路径的值顶点,而集合 Q 则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中,算法对每条外接边 (u, v) 进行拓展。

1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]                        // 初始化
 3           d[v] := infinity
 4           previous[v] := undefined
 5     d[s] := 0
 6     S := empty set
 7     Q := set of all vertices
 8     while Q is not an empty set                      // Dijkstra演算法主體
 9           u := Extract_Min(Q)  //在Q中离S最近的点,在第一次的时候,我们要先得到和S点直接连接点的距离,然后再做选择
10           S := S union {u}
11           for each edge (u,v) outgoing from u
12                  if d[v] > d[u] + w(u,v)             // 拓展边(u,v)
13                        d[v] := d[u] + w(u,v)
14                        previous[v] := u

Dijkstra's algorithm 的复杂度为 O(V^2).


http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

http://www.cnblogs.com/xiaosuo/archive/2010/03/23/1656921.html

分享到:
评论

相关推荐

    单源最短路径实验报告

    【单源最短路径】是图论中的一个重要概念,它是指在给定的带权有向图中,从一个特定的源节点出发,找到到达所有其他节点的最短路径。这个概念广泛应用于计算机科学和算法设计,特别是在网络路由、物流规划、社交网络...

    用贪心算法解单源最短路径问题

    用贪心算法解单源最短路径问题 在计算机科学和信息技术领域中,单源最短路径问题是指从一个源点到其他顶点的最短路径问题。它是一种典型的图论问题,广泛应用于交通网络、通信网络、计算机网络等领域。贪心算法是...

    分支限界法求解单源最短路径.zip

    在本案例中,我们关注的是如何利用分支限界法求解单源最短路径问题。单源最短路径问题是从一个指定的起点到图中所有其他顶点的最短路径问题,这个问题在图论和计算机科学中有广泛的应用,例如网络路由优化、物流配送...

    单源最短路径--分支限界法

    "单源最短路径--分支限界法" 单源最短路径是图论中的一种常见问题,它是指从一个源顶点到所有其他顶点的最短路径长度。这里的长度是指路上各边权之和。本文将介绍一种解决单源最短路径问题的方法,即分支限界法。 ...

    用Dijkstra算法求图中单源最短路径

    "用Dijkstra算法求图中单源最短路径" Dijkstra算法是一种常用的图搜索算法,用于解决单源最短路径问题。单源最短路径问题是指从一个出发顶点到所有可达顶点的最短路径问题。Dijkstra算法的原理是通过将图中的每个...

    分支限界法求解单源最短路径

    单源最短路径问题在图论中是一个经典问题,它要求找出从图中一个特定顶点(源点)到其他所有顶点的最短路径。在这个场景中,我们使用了分支限界法来解决这个问题。分支限界法是一种搜索算法,通常用于优化问题,它...

    贪心算法法-单源最短路径 java

    ### 贪心算法在单源最短路径问题中的应用 #### 一、问题背景与定义 本篇文章探讨的是在给定的带权有向图 \(G=(V,E)\) 中,利用贪心算法求解单源最短路径问题的方法。具体来说,问题可以这样描述:在一个带权有向图...

    单源最短路径 直接copy 运行即可,里面有测试结果

    ### 单源最短路径算法解析与应用实例 在图论和网络理论中,寻找从一个顶点到图中其他所有顶点的最短路径是一个常见的问题,这被称为单源最短路径问题。该问题在各种领域都有广泛的应用,如交通规划、网络路由选择、...

    单源最短路径vc源码(贪心算法)

    单源最短路径问题在图论中是一个经典问题,它旨在找出从图中一个特定顶点(源点)到其他所有顶点的最短路径。在这个场景中,我们提到的"单源最短路径vc源码"是用C++编程语言实现的一个贪心算法解决方案,该算法在...

    基于贪心法求解单源最短路径问题.docx

    "基于贪心法求解单源最短路径问题" 本资源是关于基于贪心法求解单源最短路径问题的实验报告,包括实验内容、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试等部分。 实验目的:理解贪心法的核心...

    单源最短路径问题C++代码

    经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径

    单源最短路径-贪心算法

    关于单源最短路径的问题非常典型,这里没有给出分析与证明,仅仅给出了实现。 需要指出的是,许多实现仅给出了最短路径的长度,而没有给出“最短路径”,这里用给出了实现。 如程序中那样,定义一个数组p[N],其中...

    单源最短路径的分支限界算法_文档.doc

    单源最短路径的分支限界算法 单源最短路径是图论中一个基本的问题,旨在寻找从某一个起始点(源点)到图中所有其他顶点的最短路径。分支限界算法是一种常用的解决单源最短路径问题的方法,本文档介绍了使用 C++ ...

    贪心算法 Dijkstra 单源最短路径

    用C++实现的贪心算法 Dijkstra 单源最短路径,并包含大量的注释,对理解程序很有帮助

    单源最短路径dijkstra模板

    单源最短路径Dijkstra模板 Dijkstra算法是一种常用的图算法,用于解决单源最短路径问题。该算法的基本思想是,通过维护一个距离数组,记录从源节点到其他所有节点的最短距离,并不断更新这些距离,使得它们变得...

    分支限界单源最短路径

    ### 分支限界单源最短路径 #### 分支限界法概述 分支限界法是一种在解决组合优化问题时常用的算法技术。它通过构造一棵状态空间树,并使用剪枝函数来减少搜索空间,从而有效地寻找最优解或者可行解。 **分支限界...

    vc关于单源最短路径(图)

    根据给定的文件信息,我们可以总结出以下有关“单源最短路径”的知识点: ### 1. 单源最短路径算法概述 单源最短路径问题是指在一个带有权重(通常为非负)的有向图或无向图中找到从一个指定顶点到所有其他顶点的...

Global site tag (gtag.js) - Google Analytics