大连海事大学现代优化技术作业dijkstra最短路径算法

《大连海事大学现代优化技术作业dijkstra最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、作业1：Dijkstra最短路径算法1120131233陈鑫交通运输工程迪杰斯特拉(Dijkstra)算法是经典路径诱导规划算法，Dijkstra算法是一个按路径长度递增的次序产生最短路径的算法，算法比较简单，容易实现，但计算量较大。1算法分析：首先引进辅助向量D,它的每个分量D[i]表示当前所找到的从始点v0到每个终点vi的最短路径的长度。为D[i]赋初值，若从W到vi有弧，则叽i]为弧上的权值，否则置D[i]为8。则长度为D[j]=Min{D[i]

2、viev}的路径就是从v0出发的长度最短的一条最短路径，

3、此路径为vO-vjo设下一条长度次短的路径的终点是vk,则这条路径或者是vO-vk,或者是vO-vj-vko它的长度是vO到vk弧上的权值或D[j]和vj到vk弧上权值之和。2算法描述：设起始点为vO,顶点集为v,初始态vievo(1)用带权邻接矩阵arcs表示带权有向图,arcs[i][j]表示弧〈vi,vj＞上的权值。若＜vi,vj＞不存在，则置arcs[i][j]为8。S为已找到从v0岀发的最短路径的终点的集合，它的初始状态为空集。从询出发到图上其余各顶点(终点)vi可能达到的最短路径长度的初值为：D[

4、i]=arcs[0][i]vieVo(2)选择vj,使得D[j]二Min{D[i]

5、viEv-s},vj就是当前求得的一条从v出发的最短路径的终点，并令S二sU{j}。(3)修改从v0出发到集合v-s上任一顶点vk可达的最短路径长度。如果D[j]+arcs[j][k]〈D[k],则修改D[k]为D[k]=D[j]+arcs[j][k]o(4)重复操作(2)、(3)共门-1次，由此求得从v0到图上其余各顶点的最短路径是一次路径长度递增的序列。3算法实现:(1)定义n为有向图中的顶点个数，arcs[i][j].w

6、为有向图中顶点i至lj顶点j的权值。首先利用如下语句为邻接矩阵赋初值，均为8。For(i-0;i

7、集。通过以下语句找到从vO出发的最短路径的终点vj,使得D[j]=Min{D[i]viev-s}for(i-0;ireturnu;上述语句中的条件语句if(find(s,i)!二1)是确保顶点vi在v-s中，find(s,1)函数的作用是若顶点vi在s中返回1,否则返回0。其代码如下：intfind(ints[HAXU]9inti)

8、AXU;j**)return0;>(4)接下来需要对己写入的最短路径长度做修改，利用下面的语句完成如果D[j]+arcs[j][k]arcs[uO

9、][u].w♦arcs[u][j].w)>s[k**]»u;(1)最后同过输出语句输出起始点vO到各个顶点的最短路径的权值和路径的顶点序列。若arcs[vO][i].w二INFINITY,贝!I表示vO到vi无穷远,无法到达。

10、«i;while(before[k]>-0&&before[k]0)printF("Zd"・i);>elseprintf(••%