最优化理论与方法 Dijsktra算法的实现.doc

最优化理论与方法课程设计

班 级： 信息与计算科学专业1102班
学 号： 1108060214
姓 名： 朱晓东
设计日期： 2013.7.5

西安科技大学计算机学院
摘 要

在实际生活当中，我们需要知道从一个城市到达另一个城市的最短路径，在旅行时可以减少在路途中的时间。路由器的路由表的更新也需要知道两个路由之间的最短距离。很多的关于两点之间的最短路径问题都可以抽象为求最短路径的数学模型。Dijkstra算法和Floyd算法是在求解最短路径问题上的最有效的算法。Dijkstra算法主要应用在求某一顶点到其余各顶点的最短路径。Floyd算法主要应用在求任意一对顶点的最短路径。本论文利用C语言实现了Dijkstra算法和Floyd算法。实际生活中的场景均可抽象成为一个有向图。程序通过实现创建有向图，以有向图作为载体实现对实际问题的求解。

关键字：最短路径，数学模型，Dijkstra算法，Floyd算法，有向图

Dijkstra算法和Floyd算法的实现

一、 算法思想

Dijkstra算法引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。Dijstra算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。
Floyd算法是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是(松弛技术)，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);其状态转移方程如下：
shorti][j]=min{short[i][k]+short[k][j],short[i][j]};
其中short[i][j]表示i到j的最短距离。

二、 流程步骤

Dijkstra算法流程：
（1） g为用邻接矩阵表示的带权图；S集合为已找到的从v0出发的最短路径终点集合，他的初始态为{v0}；dist[i]=g.arcs[0][i].
（2） 选择vk，使得dist[k]=min{dist[i]|vi∈V-S}。其中，vk就是当前求得一条从v0出发的最短路径的终点。令S=S∪{vk}。
（3） 修改从v0出发到集合V-S上任一顶点vi可达的最短路径长度。如果dist[k]+g.dist[k][i]<dist[i],则将dist[i]修改为：dist[k]+g.arcs[k][i].
（4） 重复（2）、（3）步n-1次，即可求得最短路径长度的递增长度的递增顺序，逐个求出v0到图中其他每个顶点的最短路径。

Floyd算法流程：
将vi、vj的最短的路径长度初始化为g.arcs[i][j]，然后进行如何n次比较和修正：
（1） 在vi、vj间加入顶点v0，比较（vi，v0，vj）和（vi，vj）的路径长度，取其中比较短的路径作为vi到vj的且顶点号不大于0的最短路径。
（2） 在vi到vj间加入顶点v1，得（vi,...,v1）和（v1,...,vj）。其中，（vi,...,v1）是vi到v1的且中间顶点号不大于0的最短路径；（v1,...,vj）是v1到vj的且中间顶点号不大于0的最短路径，着两条路径在上一步中已求得。将（vi,...,v1,...,vj）与上一步已求得的且vi到vj中间顶点号不大于0的最短路径比较，取其中较短的路径作为vi到vj的且中间顶点号不大于1的最短路径。
（3） 在vi、vj间加入顶点v2，得（vi,...,v2）和（v2,...,vj）。其中，（vi,...,v2）是vi到v2的且中间顶点号不大于1的最短路径；（v2,...,vj）是v2到vj的且中间顶点号不大于1的最短路径，着两条路径在上一步中已求得。将（vi,...,v2,...,vj）与上一步已求得的且vi到vj中间顶点号不大于1的最短路径比较，取其中较短的路径作为vi到vj的且中间顶点号不大于2的最短路径。
以此类推，经过n次比较和修正，在第（n-1）步将求得vi到vj的且中间顶点号不大于n-1的最短路径，这必是vi到vj的最短路径。按此方法可求得各对顶点间的最短路径。

三、源程序
//创建有向图
#include <stdio.h>
#include <stdlib.h>

typedef char VertexType;
#define MAXNODE 100 //定义最大的顶点的个数
#define INIFITY 1000 //权值无穷大

int dist[MAXNODE]; // 表示当前点到源点的最短路径长度
int prev[MAXNODE]; //表示当前节点的紧前节点

int path[MAXNODE][MAXNODE]; //表示i到j的路径
int shortDistance[MAXNODE][MAXNODE]; //表示i到j的最短路径长度

typedef struct
{
VertexType vertex[MAXNODE];
int arcs[MAXNODE][MAXNODE];
int vernum,arcnum;
}Graph; //图的结构体

void initGraph(Graph* g)
{
int i,j;
printf("请输入顶点的个数:");
scanf("%d",&g->vernum); //得到顶点的个数
for (i = 0;i<g->vernum;++i)
{
g->vertex[i] = (char)(65+i);
}

for (i = 0;i<g->vernum;++i)
for(j = 0;j<g->vernum;++j)
g->arcs[i][j] = INIFITY; //初始化 每两个点之间都是无穷大

for (i = 0;i<g->vernum;++i)
g->arcs[i][i] = 0; //对角线上的权值为0
}

int locateVertex(Graph g,VertexType vertex) //查找点的位置
{
int i;
for (i = 0;i<g.vernum;++i)
if (vertex == g.vertex[i])
return i;
return -1; //没有找到的话 返回-1
}

void createGraph(Graph* g) //创建一个无向图
{
VertexType ver1,ver2;
int weigt;
int a,b;
printf("请输入边的个数:");
scanf("%d",&g->arcnum);
fflush(stdin);
for (int i = 0;i<g->arcnum;++i)
{
printf("请输入两点和两点的权值:");
scanf("%c %c %d",&ver1,&ver2,&weigt);
fflush(stdin);
a = locateVertex(*g,ver1);
b = locateVertex(*g,ver2);
g->arcs[a][b] = weigt;
//g->arcs[b][a] = weigt;
}
}

void Dijkstra(int n, int v, int *dist, int *prev, int c[MAXNODE][MAXNODE])
{
int s[MAXNODE]; // 判断是否已存入该点到S集合中
for(int i=0; i<n; ++i)
{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用过该点
if(dist[i] == INIFITY)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;

// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
// 一旦S包含了所有V中顶点，dist就记录从源点到所有其他顶点之间的最短路径长度
// 注意是从第二个节点开始，第一个为源点
for(i=1; i<n; ++i)
{
int tmp = INIFITY;
int u = v;
// 找出当前未使用的点j的dist[j]最小值
for(int j=0; j<n; ++j)
if((!s[j]) && dist[j]<tmp)
{
u = j; // u保存当前邻接点中距离最小的点的号码
tmp = dist[j];
}
s[u] = 1; // 表示u点已存入S集合中

// 更新dist
for(j=0; j<n; ++j)
if((!s[j]) && c[u][j]<INIFITY)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}

// 查找从源点v到终点u的路径，并输出
void searchPath(int *prev,int v, int u,Graph g)
{
int que[MAXNODE]; //使用一个栈
int tot = 0;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp != v)
{
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=0; --i)
if(i != 0)
printf("%c->",g.vertex[que[i]]);
else
printf("%c\n",g.vertex[que[i]]);
}

void DijkstraPath(Graph g)
{
VertexType ch;
int flag = 1;
while (flag)
{
printf("请输入终点(以#字符结束,并显示所有的两点之间的最短路径):");
fflush(stdin);
scanf("%c",&ch);
if(ch == '#')
{
printf("\n");
return;
}
//searchPath(prev,0,locateVertex(g,ch),g);
if (dist[locateVertex(g,ch)] == INIFITY)
printf("不能到达%c点\n",ch);
else
{
searchPath(prev,0,locateVertex(g,ch),g);
printf("最短路长为%d\n",dist[locateVertex(g,ch)]);
}
}
}

void Floyd(Graph g)
{
int i,j,k;
for(i = 0;i<g.vernum;i++)
for (j = 0;j<g.vernum;j++) //初始化路径
{
if (g.arcs[i][j]<INIFITY)
path[i][j] = j; //i的后继节点为j
else
path[i][j] = -1;
shortDistance[i][j] = g.arcs[i][j];
}
for(k = 0;k<g.vernum;k++)
for(i = 0;i<g.vernum;i++)
for(j = 0;j<g.vernum;j++)
if (shortDistance[i][j]>shortDistance[i][k]+shortDistance[k][j])
{ //插入0、1、2、...n-1点
shortDistance[i][j]=shortDistance[i][k]+shortDistance[k][j];
path[i][j] = path[i][k];
}

for(i=0;i<g.vernum;i++)
{ //输出每对顶点间最短路径长度及最短路径
for(j=0;j<g.vernum;j++)
{
printf("%c到%c的最短长度:",g.vertex[i],g.vertex[j]);
printf("%d\t",shortDistance[i][j]); //输出i到j的最短路径长度
k=path[i][j]; //取路径上i的后续k
if(k==-1) //路径不存在
{
printf("There is no path between %c and %c\n",g.vertex[i],g.vertex[j]);
}
else
{
printf("最短路径为:");
printf("%c",g.vertex[i]); //输出Vi
while(k!=j){ //k不等于路径终点j时
printf("->%c",g.vertex[k]); //输出k
k=path[k][j]; //求路径上下一顶点序号
}
printf("->%c\n",g.vertex[j]); //输出路径终点序号
}
}
}
}

void main()
{
Graph g;
initGraph(&g);
createGraph(&g);
Dijkstra(g.vernum,0,dist,prev,g.arcs);
DijkstraPath(g);
Floyd(g);
}

四、 算例和结果

本演示程序用vc6.0编写，在console下完成Dijkstra算法和Floyd算法的演示。
（1）输入的形式和输入值的范围：以整数的形式输入点边的个数，以整数的形式输入边的权值。以大写字母输入顶点。
（2）输出的形式：两点之间最短路径和最短长度。
（3）程序所能达到的功能：完成Dijkstra算法和Floyd算法的演示。
（4）测试数据：
输入边数：4
‚输入顶点数：4
ƒ输入两顶点和两顶点边的权值：A B 3
输入两顶点和两顶点边的权值：B D 8
输入两顶点和两顶点边的权值：D C 6
输入两顶点和两顶点边的权值：C A 4

输入的格式如下：

下面演示以A为起点，到任意一点的距离：

下面通过Floyd算法实现任意两点之间的最短路径：

五、 总结
Dijkstra算法和Floyd算法在离散数学和数据结构中均有涉及，在最优化理论中，这两种算法都属于动态规划中的内容。动态规划的算法思想是解决多阶段决策过程最优化问题的一种方法。将复杂的问题分解成相互关联的若干阶段，每个阶段都是一个最优化子问题。在做这个程序的时候，遇到的最大的困难便是如何将这种动态的思想转化成程序。在动态规划的过程中，动态转移方程是非常关键的一个步骤，在程序中，是整个算法的集中体现。还有在程序中记录经过的顶点的位置，需要用到栈这个数据结构。程序的实现用到了很多的数据结构方面的问题，尤其是图论中的问题。我想我在这方面还是需要进一步的加强。
通过对于Dijkstra算法和Floyd算法的实现，我还需要进一步对实际问题进行解决，这样才能学以致用。对于实际问题的求解需要建立数学模型，如最短路径问题，使用Dijkstra算法可以有效地解决一点到任意一点的最短距离。

六、 参考文献

【1】李占利，张卫国编著. 最优化理论与方法[m]. 中国矿业大学出版社,2012年8月
【2】张小艳，龚尚福编著. 数据结构与算法[m]. 中国矿业大学出版社
【3】严蔚敏，吴伟民编著. 数据结构（C语言版）[m]. 清华大学出版社,2012
【4】百度百科 Dijkstra算法，Floyd算法