文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 单源最短路径问题-Dijkstra
侵权投诉

单源最短路径问题-Dijkstra

单源最短路径问题

所谓单源最短路径问题是指:已知图G=(V,E),我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。

首先,我们可以发现有这样一个事实:如果P是G中从vs到vj的最短路,vi是P中的一个点,那么,从vs沿P到vi的路是从vs到vi的最短路。

对于图G,如果所有Wij≥0的情形下,目前公认的最好的方法是由Dijkstra于1959年提出来的。

Dijkstra算法基本思想:设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

(1)初始时,S中仅含有源节点。

(2)设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,用数组D[i]记录顶点i当前所对应的最短特殊路径长度。

(3)Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组D作必要的修改。

(4)一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。 源程序1:

//Dijkstra算法

#include<iostream>

#include<cstdlib>

using namespace std;

#define VEX 5//定义结点的个数

#define maxpoint 100

double graph[][maxpoint]={

{ 0 , 10 , -1 , 30 , 100 },

{ -1 , 0 , 50 , -1 , -1 } ,

{ -1 , -1 , 0 , -1 , 10 } ,

{ -1 , -1 , 20 , 0 , 60 } ,

{ -1 , -1 , -1 , -1 , 0 }

}; //邻接矩阵

void main()

{int R[maxpoint]={0},B[maxpoint];

int D[VEX],P[VEX];//定义数组D用来存放结点特殊距离,P数组存放父亲结点 //初始时,红点集中仅有源结点0

R[0]=1; B[0]=0;

for(int i=1;i<VEX;i++)

B[i]=1;

//对数组D、P进行初始化

for(i=0;i<VEX;i++)

{D[i]=graph[0][i];

if(D[i]!=-1) P[i]=0;

else P[i]=-1;

第1页

热门文档

相关文档

  • 单源最短路径问题-Dijkstra

    Dijkstra算法Dijkstra算法隐藏>> 单源最短路径问题 所谓单源最短路径问题是指:已知图 G=(V,E) ,我们希望找出从某给定的源结点 S∈V 到 V 中的每个结点...

  • 单源最短路径问题实验参考报告

    Dijkstra算法是解决单源最短路径问题的贪心算法。设置顶点集合S并不断作 贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路 径已知。初始...

  • 求单源最短路径—Dijkstra算法实验报告

    优化问题的贪心算法,了解贪心法的基本要素,学会如何使用贪 心策略设计算法; (2)了解单源最短路径问题,掌握 Dijkstra 算法的思想; (3)编写程序,利用 Dijkstra ...

  • 计算单源最短路问题(Dijkstra算法)

    计算单源最短路问题(Dijkstra算 三、计算单源最短路问题(Dijkstra算 法)所谓单源是指一个出发顶点,单源最短路问题指的是该 顶点至所有可达顶点的最短路径问题...

  • 单源最短路径问题 徐林林4

    1 单源最短路径问题徐林林 文中首先介绍单源最 摘要: 本文对实际应用中的单...[maxPoint] , int startPoint , int size ); bool Dijkstra(); void ...

  • 【题25】计算单源最短路问题(Dijkstra算法)--试题解析

    【题25】计算单源最短路问题(Dijkstra算法)--试题解析_数学_自然科学_专业...第一组结点对应的距离值就是由 v0 到此结点的最短路径长度; 第二组结点对应...

  • 单源最短路径算法(Dijkstra算法)

    单源最短路径算法(Dijkstra算法)_IT/计算机_专业资料。关于程序... 单源最短路径问题 徐... 11页 免费 单源点最短路径的贪心算... 3页 1...

  • 单源最短路径(两种方法)

    这个问题通常称为单源最短路径问题。 2、 问题分析 推导过程(最优子结构证明,...源点 s (0 到 4 之间): "; cin >> s; head = create(); Dijkstra(...

  • 单源最短路径问题并行算法分析

    三、 实验内容 1、分析单源最短路径 Dijkstra 并行算法和 MPI 源程序。 2、分析单源最短路径问题的 Moore 并行算法,比较两种并 行算法的性能。 四、 实验步骤...

  • 单源最短路径的问题

    单源最短路径的问题_计算机软件及应用_IT/计算机_专业资料。单源最短路径的...[100];//记录从源点到i的相应最短路径 void dijkstra(int v){ if(v<1 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email