单源最短路径问题-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
#include
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 B[i]=1; //对数组D、P进行初始化 for(i=0;i {D[i]=graph[0][i]; if(D[i]!=-1) P[i]=0; else P[i]=-1; } //输出邻接矩阵 for(i=0;i {for(int j=0;j cout< cout< } //输出D、P表头 cout<<" "; for(i=0;i cout<<"D["< cout<<" "; for(i=0;i cout<<"P["< cout< for(int k=1;k { for(int min=0;B[min]==0;) min++; //求蓝点集结点最小下标元素 for(int j=min;j if(D[j]!=-1&&D[j] cout<<"min="< //将具有最短特殊路长度的结点min添加到红点集中 R[min]=1; B[min]=0; //对数组D作必要的修改 for(j=1;j if(graph[min][j]!=-1&&min!=j) //结点min到j间有路 if(D[j]>D[min]+graph[min][j]||D[j]==-1) {D[j]=D[min]+graph[min][j]; //每次迭代求最小值，最后一次即为到源点的最短路径 P[j]=min; } //输出最短路径 for(i=0;i cout< cout<<" "; for(i=0;i cout< cout< } } 源程序2: #include using namespace std; //////////////////////////////////////////////////////////// // Graph.h #define maxPoint 100 class CGraph { public: CGraph(void); ~CGraph(void); bool SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size ); bool Dijkstra(); void Display(); int GetStartPoint(); double GetBestWay( int dest , int path[] , int &pathLen ); private: bool solved;//标志当前图是否已经求解 double graph[maxPoint][maxPoint];//当前图布局 int size;//地图大小 int startPoint;//起点 double dist[maxPoint];//当前图的解 int prev[maxPoint]; }; //////////////////////////////////////////////////////////// // Graph.cpp CGraph::CGraph(void) { for( int i = 0 ; i < maxPoint ; i++ ) { for( int j = 0 ; j < maxPoint ; j++ ) graph[i][j] = -1; } startPoint = -1; size = -1; solved = false; //当前图还没有求解 } CGraph::~CGraph(void) { } // bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size ) { for( int i = 0 ; i < size ; i++ ) { for( int j = 0 ; j < size ; j++ ) graph[i][j] = g[i][j]; } this->startPoint = startPoint; this->size = size; solved = false; Dijkstra(); return true; } // bool CGraph::Dijkstra() { bool s[maxPoint]; for( int j = 0 ; j < size ; j++ ) { dist[j] = graph[startPoint][j]; s[j] = false; if( dist[j] < 0 ) //dist[i]<0，表示没有路径连接结点startPoint 与结点j prev[j] = 0; else prev[j] = startPoint; } //从起点出发 dist[startPoint] = 0; s[startPoint] = true; for( int i = 0 ; i < size ; i++ ) { double temp; int u = startPoint; bool flag = false; for( int j = 0 ; j < size ; j++ ) { if( !s[j] ) { //如果不是第一次比较，temp、u，都已经赋值，则 if( flag ) { if( dist[j] > 0 && dist[j] < temp ) { u = j; temp = dist[j]; } } else { u = j; temp = dist[j]; flag = true; } } } s[u] = true; for( j = 0 ; j < size ; j++ ) { if( !s[j] && graph[u][j] > 0 ) { double newDist = dist[u] + graph[u][j]; if( dist[j] < 0 || newDist < dist[j] ) { dist[j] = newDist; prev[j] = u; } } } } solved = true; return true; } // void CGraph::Display() { printf( "当前地图的邻接矩阵\n" ); for( int i = 0 ; i < size ; i++ ) { for( int j = 0 ; j < size ; j++ ) { printf( "%5.f" , graph[i][j] ); } printf( "\n" ); } } // double CGraph::GetBestWay( int dest , int path[] , int &pathLen ) { int p = dest; int theway[maxPoint]; int len = 0; while( p != startPoint ) { theway[len] = p; p = prev[p]; len++; } theway[len] = startPoint; len++; for( int i = 0 , j = len - 1 ; i < len ; i++ , j-- ) path[i] = theway[j]; pathLen = len; return dist[dest]; } // // int CGraph::GetStartPoint() { return startPoint; } // //////////////////////////////////////////////////////////// // Dijkstra.cpp : 定义控制台应用程序的入口点。 void main() { 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 } }; int size = 5; int start = 0; int dest = 1; int pathlen; int path[maxPoint]; double dist; CGraph g; g.SetGraph( graph , start , size ); g.Display(); printf( "----------------------------------------\n" ); for( dest = 0 ; dest < size ; dest++ ) { dist = g.GetBestWay( dest , path , pathlen ); printf( "从%d 到%d 的最短路径长%.f\n" , g.GetStartPoint() , dest , dist ); printf( "所经结点为:\n" ); for( int i = 0 ; i < pathlen ; i++ ) printf( "%3d" , path[i] ); printf( "\n----------------------------------------\n" ); } } //////////////////////////////////////////////////////////// 实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include 实验三单源最短路径 一、实验目的及要求 掌握贪心算法的基本思想 用c程序实现单源最短路径的算法 二、实验环境 Window下的vc 2010 三、实验内容 1、有向图与单源点最短路径 2、按路径长度非降的次序依次求各节点到源点的最短路径 3、Dijkstra算法 四、算法描述及实验步骤 设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧 #define MAX 999 void getdata(int **c,int n) { int i,j; int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do { cout<<"请输入起点终点权值(-1退出)："; cin>>begin; if(begin==-1) break; cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j] 实验四单源最短路径问题 一、实验目的： 1、理解分支限界法的剪枝搜索策略； 2、掌握分支限界法的算法柜架； 3、掌握分支限界法的算法步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略； 二、实验内容及要求： 1、使用分支限界法解决单源最短路径问题。 2、通过上机实验进行算法实现。 3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。 三、实验原理： 分支限界法的基本思想： 1、分支限界法与回溯法的不同： 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2、分支限界法基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3、常见的两种分支限界法： 1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 四、程序代码 #include 单源最短路径的Dijkstra算法： 问题描述： 给定一个带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 算法描述： Dijkstra算法是解单源最短路径的一个贪心算法。基本思想是：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 源代码： #include using namespace std; //-------------------------------------数据声明------------------------------------------------//c[i][j]表示边(i,j)的权 //dist[i]表示当前从源到顶点i的最短特殊路径长度 //prev[i]记录从源到顶点i的最短路径上的i的前一个顶点 //--------------------------------------------------------------------------------------------- void Dijkstra(int n, int v, int dist[], int prev[], int c[][LEN]) { bool s[LEN]; // 判断是否已存入该点到S集合中 for (int i = 1; i <= n; i++) { dist[i] = c[v][i]; s[i] = false; //初始都未用过该点 if (dist[i] == MAX) prev[i] = 0; //表示v到i前一顶点不存在 else prev[i] = v; } dist[v] = 0; s[v] = true; 单源最短路径问题 I 用贪心算法求解 贪心算法是一种经典的算法，通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。一般具有2个重要的性质：贪心选择性质和最优子结构性质。 一、问题描述与分析 单源最短路径问题是一个经典问题，给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 分析过程：运用Dijkstra算法来解决单源最短路径问题。 具备贪心选择性质 具有最优子结构性质 计算复杂性 二、算法设计（或算法步骤） 用贪心算法解单源最短路径问题： 1.算法思想： 设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 2.算法步骤： (1) 用带权的邻接矩阵c来表示带权有向图, c[i][j]表示弧 单源最短路径问题 所谓单源最短路径问题是指：已知图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 单源最短路径 计科一班李振华 2012040711 1、问题描述 给定带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 2、问题分析 推导过程（最优子结构证明，最优值递归定义） 1、贪心算法 对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra 于1959年提出来的。 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。 Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具 P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。 在叙述Dijkstra方法的具体步骤之前，说明一下这个方法的基本思想。s=1。因为所有Wij≥0，故有d(v1, v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1, v2), (v1, v3)和(v1, v4)。 （1）如果某人从v1出发沿(v1, v2)到达v2，这时需要d(v1, v1)+w12=6单位的费用； （2）如果他从v1出发沿(v1, v3)到达v3，这时需要d(v1, v1)+w13=3单位的费用； （3）若沿(v1, v4)到达v4，这时需要d(v1, v1)+w14=1单位的费用。 因为min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v1)+w14}= d(v1, v1)+w14=1，可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1, v4)，d(v1, v4)=1。这是因为从v1到v4的任一条路P，如果不是(v1, v4)，则必是先从v1沿(v1, v2)到达v2，或者沿(v1, v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij≥0)。因而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。 （4）现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1, v2)、(v1, v3)到达v2, v3，需要的费用分别为6与3，而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v4)+w46}= d(v1, v1)+w13=3。基于同样的理由可以断言，从v1 实验单源点最短路径 一、实验目的 1、深入理解贪心策略的基本思想。 2、能正确采用贪心策略设计相应的算法，解决实际问题。 3、掌握贪心算法时间空间复杂度分析，以及问题复杂性分析方法 二、实验内容 单源最短路径 三、设计分析 单源点最短路径 Dijkstra算法是解单源点最短路径的一个贪心算法。其基本思想是，设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合当且仅当从源点到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短路径特殊长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包括了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。存在一个带权有向图。 四、算法描述及程序 #include "stdafx.h" #include "iostream" using namespace std; #define N 5 #define MAX 1000 int edge1[7] = { 1, 1, 1, 2, 3, 4, 4 }; int edge2[7] = { 2, 5, 4, 3, 5, 3, 5 }; int length[7] = { 10, 100, 30, 50, 10, 20, 60 }; int c[N][N]; template 实验1. 贪心法求解单源最短路径问题 实验内容 本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试）。应用贪心策略求解有向带权图的单源最短路径问题。 实验目的 通过本次实验，掌握算法设计与分析的一般过程，以及每个步骤的基本方法。并应用贪心法求解单源最短路径问题。 环境要求 对于环境没有特别要求。对于算法实现，可以自由选择C, C++, Java，甚至于其他程序设计语言。 实验步骤 步骤1：理解问题，给出问题的描述。 步骤2：算法设计，包括策略与数据结构的选择 步骤3：描述算法。希望采用源代码以外的形式，如伪代码、流程图等； 步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明； 步骤5：算法复杂性分析，包括时间复杂性和空间复杂性； 步骤6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图; 步骤7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。 说明：步骤1-6在“实验结果”一节中描述，步骤7在“实验总结”一节中描述。 实验结果 1.问题描述 给定一个有向带全图G=（V，E），其中每条边的权是一个非负实数。另外，给定V中的一个顶点，称为源点。现在要计算源点到所有其他各个顶点的最短路径长度，这里的路径长度是指路径上所有经过边的权值之和。这个问题通常称为单源最短路径问题。 2.（1)Dijkstra算法思想 按各个结点与源点之间路径长度的非减次序，生成源点到各个结点的最短路径的方法。 即先求出长度最短的一条路径，再参照它求出长度次短的一条路径。依此类推，直到从源点到其它各结点的最短路径全部求出为止。 1959年提出的，但当时并未发表。因为在那个年代，算法基本上不被当做一种科学研究的问题。 （2）Dijkstra算法设计 集合S与V-S的划分：假定源点为u。集合S中的结点到源点的最短路径的长度已经确定，集合V-S中所包含的结点到源点的最短路径的长度待定。 特殊路径：从源点出发只经过S中的结点到达V-S中的结点的路径。 贪心策略：选择特殊路径长度最短的路径，将其相连的V-S中的结点加入到集合S中。3、描述算法 Dijkstra算法的伪代码： DIJKSTRA(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) S = Φ Q = G.V //V-S中的结点按特殊路径长度非减排序 while Q ≠Φ u = EXTRACT-MIN(Q) S = S ∪{u} for each v∈G.Adj[u] RELAX(u, v, w) 4、Dijkstra算法的求解步骤： 步骤1：设计合适的数据结构。带权邻接矩阵C记录结点之间的权值，数组dist来记录从源点到其它顶点的最短路径长度，数组p来记录最短路径。u为源点； 步骤2：初始化。令集合S={u}，对于集合V-S中的所有顶点x，设置dist[x]=C[u][x]。如果顶点x与源点相邻，设置p[x]=u；否则，p[x]=-1； 步骤3：贪心选择结点。在集合V-S中依照贪心策略来寻找使得dist[x]具有最小值的顶点t，t就是集合V-S中距离源点u最近的顶点。 步骤4：更新集合S和V-S。将顶点t加入集合S中，同时更新集合V-S； 步骤5：判断算法是否结束。如果集合V-S为空，算法结束。否则，转步骤6； 步骤6：对相关结点做松弛处理。对集合V-S中的所有与顶点t相邻的顶点x，如dist[x]>dist[t]+C[t][x]，则dist[x]=dist[t]+C[t][x]并设置p[x]=t。转步骤3。 5、Dijkstra算法的正确性证明–贪心选择性质： 采用归纳法。当S={s, p}时，则除源结点s之外的所有结点中，结点p到源点s的距离最短。这是显然的。 假设当S={s, p1, …, pk}时，即k个结点p1, …, pk到源点s的距离最短。当S={s, p1, …, pk, pk+1}时，很显然结点pk+1到源点s的距离是最短的。需证明：此时结点p1, …, pk到源点s的距离仍然是最短的。用反证法假设当结点pk+1加入到S后，pi结点经由结点pk+1到源点s的距离更短，即d(s, pk+1) + d(pk+1, pi) < d(s, pi)，有d(s, pk+1) < d(s, pi) ，则结点pk+1 单源最短路径问题并行算法分析实验报告 一、实验名称 单源最短路径问题并行算法分析。 二、实验目的 分析单源最短路径Dijkstra并行算法和MPI源程序，并分析比较Dijkstra并行算法和Moore并行算法的性能。 三、实验内容 1、分析单源最短路径Dijkstra并行算法和MPI源程序。 2、分析单源最短路径问题的Moore并行算法，比较两种并行算法的性能。 四、实验步骤 1、问题描述 单源最短路径问题即指：已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其他各个结点的最短路径。这里还假定所有的权值都是正的。 2、比较串行Dijkstra算法和Moore算法 2.1、Dijkstra算法基本思想 假定有一个待搜索顶点表VL，初始化时做：dist(s)←0；dist(i)←∞(i≠s)；VL←V。算法执行时，每次从VL（≠Φ）中选取这样一个顶点u，它的dist(u)值最小。将选出的u作为搜索顶点，若 一、实验名称：单源最短路径问题 时间：X年X月X日，星期3，第三、四节 地点：0#601 二、实验目的及要求 1、掌握分支限界法解题步骤： 1在问题的边带权的解空间树中进行广度优先搜索 2找一个叶结点使其对应路径的权最小(最大) 3当搜索到达一个扩展结点时,一次性扩展它的所有儿子 4将满足约束条件且最小耗费函数目标函数限界的儿子,插入活结点表中 5从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表 为空为止 三、实验环境 Window下的vs2010 四、实验内容 单源最短路径问题 以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。 求图G的从源顶点s到目标顶点t之间的最短路径 五、算法描述及实验步骤 算法思想： 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点i到j有边可达，且从源出发，途经i再到j的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 结点扩展过程一直继续到活结点优先队列为空时为止 二．单源最短路径问题 1.问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。 2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 福州大学数学与计算机科学学院 《计算机算法设计与分析》上机实验报告（5） 个大数。dist[i]表示当前从源到顶点i的最短特殊路径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u 之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i，则这种路的最短长度是dist[u]+c[u][i]。如果 dist[u]+c[u][i] 数据结构课程设计 设计说明书 数学与计算机科学学院 2014年3月7日 单源点最短路径算法的实现 学生姓名 潘 飞 学 号 1221024012 班 级 信管1201班 成 绩 指导教师 余冬梅 课程设计任务书 2013 —2014 学年第2 学期 专业：信息管理与信息系统学号：1221024030 姓名：潘飞 课程设计名称：数据结构课程设计 设计题目：单源点最短路径算法的实现 完成期限：自2014 年 2 月24 日至2014 年 3 月7 日共 2 周 设计依据、要求及主要内容（可另加附页）： 最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然后依次把未知集合的顶点按照最短路径（特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚）加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题，这对以上几个问题采用了迪杰斯特拉算法。并为本系统设置一人性化的系统提示菜单，方便使用者的使用。 本课程设计中主要完成以下内容： 1. 建立图的存储结构。 2. 解决单源最短路径问题。 3.实现两个顶点之间的最短路径问题。 基本要求如下： 1.程序设计界面友好； 2.设计思想阐述清晰； 3.算法流程图正确； 4.软件测试方案合理、有效。 指导教师（签字）：教研室负责人（签字）： 批准日期：年月日 课程设计评阅 评语： 指导老师签名： 年月日 实验题目：单源最短路径问题2010年11月18日告诉您寝的人下周二（13周）做实验记得写~~~~ 实验目的： 1．明确单源最短路径问题的概念； 2．利用贪心算法解决单源最短路径问题； 3．通过本例熟悉贪心算法在程序设计中的应用方法。 实验内容 给定一个带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其他各点的最短路长度。 实验原理 在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策。 Dijkstra算法是解决单源最短路径问题的贪心算法。设置顶点集合S并不断作 贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径已知。初始时S中只含源。设u为G中一顶点，从源点到u且中间只经过S中的顶点的路称为从源到u特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解。 算法实现 #include c[i][j]=MAX; } } do { cout<<"请输入起点终点权值(-1退出)："; cin>>begin; if(begin==-1) break; cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j] 最短路径算法及应用 乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 一种可能的方法就是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。那么我们很容易看到，即使不考虑包含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是不值得考虑的。 在这一章中，我们将阐明如何有效地解决这类问题。在最短路径问题中，给出的是一有向加权图G＝（V，E，W），其中V为顶点集，E为有向边集，W为边上的权集。最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。 一、单源最短路径问题 所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V 到V中的每个结点的最短路径。 首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。 （一）Dijkstra算法 对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。 例1 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。 Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个 点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P 标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T 标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。 在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。例1中，s=1。因为所有Wij≥0，故有d(v1, v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1, v2), (v1, v3)和(v1, v4)。如果某人从v1出发沿(v1, v2)到达v2，这时需要d(v1, v1)+w12=6单位的费用；如果他从v1出发沿(v1, v3)到达v3，这时需要d(v1, v1)+w13=3单位的费用；类似地，若沿(v1, v4)到达v4，这时需要d(v1, v1)+w14=1单位的费用。因为min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v1)+w14}= d(v1, v1)+w14=1，可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1, v4)，d(v1, v4)=1。这是因为从v1到v4的任一条路P，如果不是(v1, v4)，则必是先从v1沿(v1, v2)到达v2，或者沿(v1, v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij≥0)。因而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1, v2)、(v1, v3)到达v2, v3，需要的费用分别为6与3，而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v4)+w46}= d(v1, v1)+w13=3。基于同样的理由可以断言，从v1到v3的最短路是(v1, v3)，d(v1, v3)=3。这样又可以使点v3变成具P 标号的点，如此重复这个过程，可以求出从v1到任一点的最短路。 在下述的Dijstra方法具体步骤中，用P，T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个λ值，算法终止时λ(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果λ(v)=∞，表示图G中不含从Vs到v的路；λ(Vs)=0。 Dijstra方法的具体步骤： {初始化} i=0 S0={Vs}，P(Vs)=0 λ(Vs)=0 对每一个v<>Vs，令T(v)=+ ∞，λ(v)=+ ∞， k=s {开始} ①如果Si=V，算法终止，这时，每个v∈Si，d(Vs,v)=P(v)；否则转入② ②考察每个使(Vk,vj)∈E且vj Si的点vj。 如果T(vj)>P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把λ(vj)修改为k。 ③令 如果，则把的标号变为P标号，令 ，k=ji，i=i+1，转①，否则终止，这时对每一个v∈Si，d(vs,v)=P(v)， 最短距离算法（Dijkstra）设计与编程实现 所在系（院）： 专业： 班级： 学号： 姓名： 绪论 随着知识经济的到来，信息将成为人类社会财富的源泉，网络技术的飞速发展与广泛应用带动了全社会对信息技术的需求，最短路径问题作为许多领域中选择最有问题的基础，在电子导航，交通旅游，城市规划以及电力、通讯等各种管网、管线的布局设计中占有重要地位。 最短路径，顾名思义就是在所有的路径中找到距离最短的路径，而我们所说的最短路径通常不仅仅指地理意义的距离最短，还可以引申到其他的度量，如时间、费用、路线容量等。相应地，最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看做是最优路径问题。 最短路径问题在交通网络结构的分析，交通运输线路的选择，通讯线路的选择与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还应用于汽车导航系统以及各种应急系统等，这些系统一般要求计算出到出事点的最佳线路，在车辆行驶过程中还需要实时的计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效的。 最短路径问题一直是计算机学科，运筹学，交通工程学，地理信息学等学科的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断的涌现。 1 定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描述：在无向图G=(V,E) 中，假设每条边E[i] 的长度为w[i]，找到由顶点V0 到其余各点的最短路径。（单源最短路径） 2 概要设计和数据结构选择 按路径长度递增的顺序产生最短路径。通过以上对问题的分析和任务的理解，设计出一个大体的模块和程序流程。 2.1程序中涉及到的结构体及子函数： 2.1.1结构体： 本程序设计使用了以下结构体： struct vertex { int num; //顶点编号 int data; //顶点信息 }; //顶点类型 typedef struct graph { int n; //图中顶点个数 int e; //图中边的个数 struct vertex vexs[MAXVEX]; //顶点集合 int edges[MAXVEX][MAXVEX]; //边的集合 }AdjMaxix; //图的邻接矩阵类型 2.1.2子函数： 设计本程序需分成几个模块，要用到以下几个子函数： AdjMaxix creatmgraph() //通过用户交互产生一个有向图的邻接矩阵； void dispmgraph(AdjMaxix adj)//用于输出一个有向图的邻接矩阵；分支限界法实现单源最短路径问题
单源最短路径 贪心算法
单源最短路径问题
单源最短路径的Dijkstra算法
单源最短路径
单源最短路径问题-Dijkstra
单源最短路径(两种方法)
算法-单源点最短路径-Dijkstra算法
实验1.-贪心法求解单源最短路径问题
单源最短路径问题并行算法分析
单源最短路径分支限界
单源最短路径算法
单源点最短路径算法的实现
单源最短路径问题实验参考报告
(完整word版)最短路径算法附应用
最短路径算法