文档章节

Dijkstra算法

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 437
阅读 9
收藏 1

算法描述

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

步骤

a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则{u,v}正常有权值,若u不是v的出边邻接点,则{u,v}权值为∞。

b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

执行动画:

这里写图片描述

具体的实例:

这里写图片描述

实例的步骤:

这里写图片描述
参考:
july的博客:
http://blog.csdn.net/v_JULY_v/article/details/6096981
其他:
http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
荷兰资格最老的程序员告诉你,如何用短短20分钟影响整个20世纪

  保持对同一个问题的思考   在那一个瞬间找到了答案   一个既是贪心又是最优的最短路径算法   1   人们总是在做一件事情:   找最短路径      公元前32世纪,苏美尔人在粘土...

超级数学建模
01/23
0
0
Dijkstra算法|单源最短路径|贪心算法

单愿最短路径描述:给定带权有向图G=(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到...

掬一捧
2012/09/26
0
0
1.1.1最短路(Floyd、Dijstra、BellmanFord)

转载自hr_whisper大佬的博客 一、Dijkstra 比较详细的迪杰斯特拉算法讲解传送门 Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。 使用邻...

fire_to_cheat_
03/04
0
0
像名字一样容易忘记的Dijkstra

Dijkstra算法是经典的求解一个顶点到其他顶点的最短距离的算法。每次学习的时候总是觉得思路简单明了,但每当要用到时,就忘记了实现的细节。归根结底还是应用的少。相信做地图导航的应该对其...

dugangabc
2016/02/06
0
0
Johnson 全源最短路径算法

前言 上一篇文章已经阐述了Floyd-Warshall算法,适用于存在负权重路径的稠密图。本文讲述的算法适用于稀疏图。 全源最短路径求解其实是单源最短路径的推广,求解单源最短路径的两种算法时间复...

某昆
2017/12/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

sourcetree 离线免注册登录安装教程

Sourcetree是一个优秀的git可视化管理工具,深受开发者喜爱Sourcetree官网,但是在安装时需要谷歌账户登录,需要翻qiang才可以,此一点一直被人们所诟病。今天本教程就为大家提供离线免登陆安...

QQZZFT
13分钟前
0
0
使用 PostgreSQL 解决一个实际的统计分析问题

使用 PostgreSQL 解决一个实际的统计分析问题作者:老农民(刘启华)Email: 46715422@qq.com 之前有个朋友扔给我一个奇葩需求,他们公司之前做了一批问卷调查,全部都是统一格式的excel...

新疆老农民
16分钟前
0
0
TypeScript基础入门之高级类型的映射类型

转发 TypeScript基础入门之高级类型的映射类型 高级类型 映射类型 一个常见的任务是将一个已知的类型每个属性都变为可选的: interface PersonPartial {    name?: string;    age?...

durban
31分钟前
0
0
Dubbo源码分析(6):Dubbo内核实现之基于SPI思想Dubbo内核实现

SPI接口定义 定义了@SPI注解 package com.alibaba.dubbo.common.extension; import java.lang.annotation.Documented;import java.lang.annotation.ElementType;import java.lang.an......

郑加威
31分钟前
0
0
RxJS的另外四种实现方式(后记)—— 同时实现管道和链式编程

目录 RxJS的另外四种实现方式(序) RxJS的另外四种实现方式(一)——代码最小的库 RxJS的另外四种实现方式(二)——代码最小的库(续) RxJS的另外四种实现方式(三)——性能最高的库 Rx...

一个灰
34分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部