最短路径算法——Dijkstra算法.doc

最短路径算法Dijkstra算法 最短路径算法是图论中应用最广的算法之一。许多实际问题只需要简单的数学模型转换，它就成为一个最短路径问题。例如，从城市甲到城市乙，需要经过许多站点和不同路径、怎样选择行走路线。使从甲城市到乙城市所经过的路径最短；如果是乘公交车，那么又有怎样选择乘车方法，使费用最少或时间最短以到达目的地等。这些都是一些典型而又直接的最短路径问题。 在图的最短路径算法中，应用最广泛和最著名的算法就是Dijkstra算法，它是一个单源点的最短路径算法。所谓单源点最短路径问题是：给定带权有向图G=(V,E)和源点S，求源点s到图G中其他各个顶点的最短路径。 Dijkstra算法是一个典型的贪心算法，同时也用了动态规划的思想。它的基本思路是：按源点s到其他各个顶点的最短路径的递增顺序，依次求出第1个最短路径p 1,第2最短路径 p 2, 在求第k最短路径p k 时，需要用到已求出第1、第2、第k 1最短路径。将基本思路转换成数学语言就是：1、 求出第一最短路径：c (s, u1)=minc (s,u) | E，其中c(u,v)为边(u,v)的权值。则路径p 1 = c (s, u1)是源点s到u1的最短路径。2、假设第1、2、3、k 1最短路径p 1、p 2、p 3、p k-1已经求出，分别对应的是s到u1、u2、u3u k-1的最短路径，那么第k最短路径可由下列公式求出：P k=min minc (s,u) | E,minp i+c(u i,u) , E而且u i u1、u2、u3u k-1由此可以求出第k最短路径P k。根据上述思想，由此可以得到如下Dijkstra算法：1、 先将数据初始化，使dist数组中全为0；设无穷大为1000；2、 遍历节点，从源节点开始，标志遍历过后节点为1；3、 设置源节点的值为1000，遍历源点，根据权值确定被源点指向的节点是最短路径。4、 依次遍历第2、3n节点，遍历时权值需要进行比较，取最短权值，并更新此节点的最短路径，直到遍历结束。下面是Dijkstra算法： void dijkstra(int *dist,int mLength,bool *s,int u)if(u6)return;int i,j,temp;for(i=0;iLength;i+)disti = 0;si = false;*(s+u) = true; temp = 1000;distu = temp;for(i=1;iLength;i+)if(!si)if(mui!=0)disti = mui;elsedisti = temp;for(j=1;jLength;j+)temp = 1000;for(i=1;idisti)temp = disti;u = i;su = true;for(i=1;iLength;i+)if(!si&mui!=0)int newdist = mui+distu;if(newdistdisti)disti = newdist;现在取单源有向图举例加以说明，解释Dijkstra算法是怎样执行的：23145101010030205060图一将此图转换成矩阵，存储该图中的权值，两节点不相接的权值设为0，图中共5个节点，矩阵如下：0 10 0 30 1000 0 50 0 00 0 0 0 100 0 20 0 600 0 0 0 0开始遍历前，初始化dist数组为0，遍历源节点后，各节点的值为;1000 10 1000 30 100 将其转化为图：231451010100302050100010001003010图二遍历源节点后，将其标志为1，表示已经遍历，不需要再遍历。然后遍历第二个节点，比较权值大小，也就是用50和1000比较，然后更改3中的值为60。此时2节点中的值为10，还需加上50才是3中目前的最短路径。遍历第二个节点后，各节点中的值变为;1000 10 60 30 100。转化成图为：231451010100302050100060100301060图三遍历第三个节点，第五个节点的最短路径需要根据第四最短路径来求，第三次遍历后，各节点的值变为：1000 10 50 30 90。转化为图为：23145101010030205010005090301060 图四然后第四次遍历，比较各权值，取最小，并更改各节点的值。第四次遍历后，各节点值为：1000 10 50 30 60 将其转化为图：23145101010030205010005060301060图五最后进行第五次遍历，因为每次遍历过后都将其节点标志设为1，图中共5个节点，当遍历到源点时，程序停止，并输出源点到各节点的最短路径。第五次遍历后，各节点值为1000 10 50 30 60 这些值也就是源点到各节点的最短路径，将其转化为图：23145101010030205010005060301060图六其中图中各节点旁的数据为源点到该节点的最短路径，图中红色加粗的线代表源点到各节点所走的最短路路径。Dijkstra完整程序代码如下： #include stdafx.h#include stdafx.h#define Length 6void dijkstra(int *dist,int mLength,bool *s,int u)if(u6)/异常输入return;int i,j,temp;for(i=0;iLength;i+)/初始化数据disti = 0;si = false;*(s+u) = true;/将源点的标志设为true，表示该点已经遍历temp = 1000;/最大值distu = temp;for(i=1;iLength;i+)/初始化dist数组if(!si)if(mui!=0)disti = mui;elsedisti = temp;for(j=1;jLength;j+)/算法开始temp = 1000;for(i=1;idisti)temp = disti;u = i;printf(%dn,disti);su = true;for(i=1;iLength;i+)/更新distif(!si&mui!=0)int newdist = mui+distu;if(newdistdisti)disti = newdist;int main(int argc, char* argv)FILE *f;int mLengthLength;if(f = fopen(a2.txt,r)=NULL)printf(cant open file);return 0;int i,j;int distLength;bool sLength;for(i=1;iLength;i+)/初始化图列表for(j=0;jLen