文档章节

数学:Dijkstra算法

pricker
 pricker
发布于 2015/09/12 19:03
字数 612
阅读 125
收藏 1

 

一.最短路径的最优子结构性质

   该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

   假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

 

二. Dijkstra算法

    Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。

 

先给出一个无向图

用Dijkstra算法找出以A为起点的单源最短路径步骤如下

 

三. 代码

Java

static int[] testDijkstra(int n,int v,int[] dist,int[] prev,int[][] c){
  
  int maxnum = 100;
  int maxint = 999999;
  
  boolean[] s = new boolean[maxnum];    // 判断是否已存入该点到S集合中
  for(int i=1; i<=n; ++i)
  {
   dist[i] = c[v][i];
   s[i] = false;     // 初始都未用过该点
   if(dist[i] == maxint)
    prev[i] = 0;
   else
    prev[i] = v;
  }
  dist[v] = 0;
  s[v] = true;
  
  // 依次将未放入S集合的结点中,取dist[]最小值的结点,放入结合S中
  // 一旦S包含了所有V中顶点,dist就记录了从源点到所有其他顶点之间的最短路径长度
          // 注意是从第二个节点开始,第一个为源点
  for(int i=2; i<=n; ++i)
  {
   int tmp = maxint;
   int u = v;
   // 找出当前未使用的点j的dist[j]最小值
   for(int j=1; j<=n; ++j)
    if((!s[j]) && dist[j]<tmp)
    {
     u = j;              // u保存当前邻接点中距离最小的点的号码
     tmp = dist[j];
    }
   s[u] = true;    // 表示u点已存入S集合中
  
   // 更新dist
   for(int j=1; j<=n; ++j)
    if((!s[j]) && c[u][j]<maxint)
    {
     int newdist = dist[u] + c[u][j];
     if(newdist < dist[j])
     {
      dist[j] = newdist;
      prev[j] = u;
     }
    }
  }
  
  return dist;
 }

 

 

© 著作权归作者所有

pricker
粉丝 7
博文 56
码字总数 33145
作品 0
渭南
私信 提问
你所不知道的 Dijkstra - 知乎

Dijkstra 的全名叫 Edsger Wybe Dijkstra。大部分中国程序员如果能记住这个名字是因为学过计算最短路径的 Dijkstra 算法,然而大部分人都难以记住正确的拼写,因为他是荷兰人,名字不符合英语...

The LeanCloud Journey
04/30
0
0
Dijkstra算法的思想和数学归纳法

ospf协议很多人都知道,很多人也会配置而且很熟练,但是很少有人懂得其背后的思想是什么,Dijkstra算法是求解单源最短路径的绝妙算法之一,我打心眼里头喜欢这个算法,真想把之一去掉。Dijks...

晨曦之光
2012/04/10
522
0
你不知道的关于计算机大师 Dijkstra 的事情

Dijkstra 的全名叫 Edsger Wybe Dijkstra(艾兹赫尔·韦伯·戴克斯特拉)。大部分中国程序员如果能记住这个名字是因为学过计算最短路径的「Dijkstra 算法」,然而大部分人都难以记住正确的拼...

oschina
2016/04/27
12.8K
25
荷兰资格最老的程序员告诉你,如何用短短20分钟影响整个20世纪

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

超级数学建模
2018/01/23
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
11
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部