杜衡吉
摘要:最短路径算法在各领域应用广泛,大多《离散数学》的图论部分最短路径算法讲解较为粗略,不便于学生学习和实践。经过多年教学总结,对最短路径算法给出设计和实现,有利于学生对本知识的掌握和实践应用。
关键词:最短路径;离散数学; Dijkstra算法
中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2016)28-0079-02
1 概述
最短路径问题是指在一个非负权值图中找出两个指定节点间的一条权值之和最小的路径。Dijkstra 算法在很多计算机专业可均有介绍,如数据结构,离散数学等,但大都比较粗略。迪克斯特拉算法是经典的求解最短路径问题的方法,是按路径长度递增的次序来产生最短路径的算法[1]。
最短路径问题描述:设n,m带权图 G=
2 最短路径概念
带权图G=
3 Dijkstra算法描述
1)算法基本过程:设带权图G=
2)算法具体步骤:
a.初始时,V1只包含源点,即V1={ v0},v0的距离为0。V2包含除v0外的其他顶点,即: V2={ v1, v2…,vn-1}。定义集合V2中的顶点的距离:若v0与V2中顶点v有边,则dist(v)=w(v0,v)正常有权值,若v0与v点不相邻,则dist(v)= ∞。
b.从V2中选取一个点k加入V1中,选择公式dist(k)=min(dist(v) | v∈U),把k加入V1中(该选定的距离就是v0到k的最短路径长度)。此时V1= V1∪{k},同时V2集合中删除k点,即V2= V2-{k}。
c.以k为新考虑的中间点,修改V2中各顶点的距离;若从源点v0到顶点v的距离(经过顶点k)比原来距离短,则修改顶点 v的距离值,否则v的距离值不变,修改公式dist(v)=min{dist(v),dist(k)+dist(k,v)}[3]。
d.重复步骤b和c直到V1=V,算法停止。
4 算法实例
1)先给出一个无向图G=
用Dijkstra算法找出以A为起点的单源最短路径步骤如表1:
5 算法代码实现
测试案例如图2所示:
#include
#include
#define M 100
#define N 100
using namespace std;
typedef struct node
{int m[N][M]; //邻接矩阵
int n; //顶点数
int e; //边数
}MGraph;
void Dpath(MGraph g,int *dist,int *path,int v0) //v0表示源点
{int i,j,k;
bool *ved=(bool *)malloc(sizeof(bool)*g.n);
for(i=0;i {if(g.m[v0][i]>0&&i!=v0) {dist[i]=g.m[v0][i]; path[i]=v0; } //path记录最短路径上从v0到i的前一个顶点 else {dist[i]=INT_MAX; //若i不与v0直接相邻,则权值置为无穷大 path[i]=-1; } ved[i]=false; path[v0]=v0; dist[v0]=0; } ved[v0]=true; for(i=1;i {int min=INT_MAX; int u; for(j=0;j {if(ved[j]==false&&dist[j] { min=dist[j]; u=j;} } ved[u]=true;
for(k=0;k { if(ved[k]==false&&g.m[u][k]>0&&min+g.m[u][k] {dist[k]=min+g.m[u][k]; path[k]=u; }}}} void Apath(int *path,int v,int v0) //打印最短路径上的各个顶点 {stack int u=v; while(v!=v0) { s.push(v); v=path[v]; } s.push(v); while(!s.empty()) {cout< s.pop();}} int main(int argc, char *argv[]) { int n,e; //表示输入的顶点数和边数 while(cin>>n>>e&&e!=0) {int i,j; int s,t,w; //表示存在一条边s->t,权值为w MGraph g; int v0; int *dist=(int *)malloc(sizeof(int)*n); int *path=(int *)malloc(sizeof(int)*n); for(i=0;i for(j=0;j g.m[i][j]=0; g.n=n; g.e=e; for(i=0;i {cin>>s>>t>>w; g.m[s][t]=w; } cin>>v0; //输入源顶点 Dpath(g,dist,path,v0); for(i=0;i {if(i!=v0) { Apath(path,i,v0); cout< return 0; } 测试结果如图3所示: 6 小结 作为一门计算机的专业基础课《离散数学》在计算机学科领域中发挥了重要的作用。最短路径算法在很多方面有着重要的应用,针对教材中Dijkstra最短路径算法讲解粗略,学生学习困难等问题,本人结合多年的教学经验,对Dijkstra算法求最短路径给出了详细的算法设计和实现,对这部分内容的教学帮助明显。 参考文献: [1] 李妍妍.Dijkstra最短路径分析算法的优化实现[J].测绘与空间地理信息,2014,37(5):172-190. [2] 耿素云,屈婉玲,张立昂.离散数学[M]. 5版.北京:清华大学出版社,2013:128-130. [3] 曹晓东,原旭.离散数学及算法 [M].北京:机械工业出版社,2012:240-244.