最近因为辞职，有不少闲功夫，重温下数据结构，顺便练练手。今天说说最短路径搜索算法中的Dijkstra原理和实现。
一：简介
这个算法用于解决图中单源最短路径问题。所谓单源节点是指给定源节点，求图中其它节点到此源节点的最短路径。如下图所示：给定源节点a，求节点b到a的最短距离。
【图论（最短路径搜索--Dijkstra算法(c代码实现)）】
文章图片

(图来自于参考资料2)
那么如何寻找？还是以上图为例：
1）初始化：设定除源节点以外的其它所有节点到源节点的距离为INFINITE(一个很大的数)，且这些节点都没被处理过。
2）从源节点出发，更新相邻节点(图中为2，3，6)到源节点的距离。然后在所有节点中选择一个最段距离的点作为当前节点。
3）标记当前节点为done(表示已经被处理过)，与步骤2类似，更新其相邻节点的距离。(这些相邻节点的距离更新也叫松弛，目的是让它们与源节点的距离最小。因为你是在当前最小距离的基础上进行更新的，由于当前节点到源节点的距离已经是最小的了，那么如果这些节点之前得到的距离比这个距离大的话，我们就更新它)。
4）步骤3做完以后，设置这个当前节点已被done，然后寻找下一个具有最小代价(cost)的点，作为新的当前节点，重复步骤3.
5)如果最后检测到目标节点时，其周围所有的节点都已被处理，那么目标节点与源节点的距离就是最小距离了。如果想看这个最小距离所经过的路径，可以回溯，前提是你在步骤3里面加入了当前节点的最优路径前驱节点信息。
看文字描述显得苍白无力，你可以结合上图，看下这个视频：http://v.youku.com/v_show/id_XMjQyOTY1NDQw.html (dijkstra演示)，然后就清楚了。

二：源代码
直接给源代码，注释很清楚，不解释。


文章图片

文章图片
Dijkstra.h

1 #ifndef _DIJKSTRA_H 2 #define _DIJKSTRA_H 3 4 #define MAX_VERTEX_NUM 100//最大顶点数 5 #define MAX_EDGE_NUM 50//相邻最大节点数 6 #define INFINITE 1E5//表示节点之间无连接的一个较大的数 7 #define MAX_STRLEN 256//最大字符串字节数 8 9 #define FALSE0 10 #define TRUE1 11 typedef intBOOL; 12 typedef unsigned intUINT; 13 14 #define SAFEFREE(p) {if(NULL!=(p)) free(p); } 15 16 extern int g_node_num; //一个图中，实际节点数的全局变量 17 typedef struct _vertex {//通用的顶点数据结构体 18int id; //id 19struct _vertex *pLinkList[MAX_EDGE_NUM]; //相邻顶点的指针数组 20int nCost[MAX_VERTEX_NUM]; //与相邻顶点的权重数组 21struct _vertex **next; //与剩余顶点之间的最短路径 22int *pmincost; //与剩余顶点之间的最小代价 23 }vertex; 24 25 typedef struct _node {//组成图的顶点元素信息进行封装 26int nID; 27struct _vertex *pVer; 28 }node; 29 30 BOOL InitGraphic(char path[], node arr[], UINT nsize); 31 void UnitGraphic(node arr[]); 32 void ViewGraphic(node arr[]); 33 BOOL Dijkstra(node arr[]); 34 void MinRoute(node arr[], UINT nSrID, UINT nDsID); 35 36 #endif

文章图片

文章图片
Dijkstra.c

1 #include 2 #include 3 #include 4 #include "Dijkstra.h" 5 6 int g_node_num; /*用于计算实际节点数的全局变量*/ 7 /**************************************** 8 *函数名：InitGraphic 9 *参数：path-图的信息文件路径；arr-储存图的数组；nsize-数组大小 10 *返回值：BOOL-成功返回1，错误返回0 11 *说明：根据图的信息文件，初始化数组 12 *****************************************/ 13 BOOL InitGraphic(char path[], node arr[], UINT nsize) 14 { 15char buf[MAX_STRLEN]; 16char *pos; 17char ctemp; 18int ncost; 19int i; 20UINT nid; //临时顶点ID 21UINT ncid; //临时连接顶点的ID 22UINT nlinkpos; //连接顶点数组中的位置 23 24memset(arr, 0, sizeof(node)*nsize); //赋值0 25FILE *pfile = fopen(path, "r"); 26if(NULL == pfile) { 27printf("Error opening file.\n"); 28return FALSE; 29} 30while(NULL != fgets(buf, MAX_STRLEN, pfile)) { 31pos = strtok(buf, ":"); //读取一行，解析第一个冒号之前的标号，即第几个节点 32nid = atoi(pos); 33if(nid < nsize) { 34arr[nid-1].nID = nid; 35arr[nid-1].pVer = (vertex*)malloc(sizeof(vertex)); //申请一个顶点struct 36if(NULL == arr[nid-1].pVer) { 37printf("out of memory!\n"); 38return FALSE; 39} 40memset(arr[nid-1].pVer, 0, sizeof(vertex)); //赋值0 41arr[nid-1].pVer->id = nid; 42g_node_num++; //节点数加1 43} else { 44fprintf(stderr, "access the boundary of setting:%d\n", nid); 45} 46} 47rewind(pfile); //文件指针跳转到开始处，读取各顶点的相邻节点 48for(i=0; i nsize || ncost < 0) { 54fprintf(stderr, "access the boundary of setting or find negative cost:%u-%d\n", ncid, ncost); 55return FALSE; 56} 57 58arr[nid-1].pVer->pLinkList[nlinkpos] = arr[ncid-1].pVer; /*相邻节点指针数组赋值*/ 59arr[nid-1].pVer->nCost[ncid-1] = ncost; /*此节点到相邻节点的cost*/ 60arr[nid-1].pVer->pmincost = NULL; 61arr[nid-1].pVer->next = NULL; 62nlinkpos++; 63} 64} 65fclose(pfile); 66return TRUE; 67 } 68 /******************************************* 69 *函数名：ViewGraphic 70 *参数：arr-图的数组 71 *返回值：无 72 *说明：打印图的结构信息 73 *******************************************/ 74 void ViewGraphic(node arr[]) 75 { 76int i, j; 77int nidtemp; //临时节点序号 78printf("\nID\tConnceted to-ID:cost"); 79for(i=0; ipLinkList[j] != NULL; j++) { 82nidtemp = arr[i].pVer->pLinkList[j]->id; 83printf("%d:", nidtemp); 84printf("%d ",arr[i].pVer->nCost[nidtemp-1]); 85} 86} 87 } 88 /************************************************* 89 *函数名：Dijkstra 90 *参数：arr-图的数组 91 *返回值：TRUE-成功；FALSE-失败 92 *说明：依次将每个节点作为起始节点，计算剩余节点与其之间的最短路径 93 *************************************************/ 94 BOOL Dijkstra(node arr[]) 95 { 96UINT i, j, k; 97vertex *pbegin, *ptemp, *ptemp1; 98int *tcost; //用于储存其余节点到起始节点的最小代价 99BOOL *pbDone; //用于判断节点是否计算完毕的数组 100int nidtemp; //与当前节点相邻的其它节点中，cost最小的顶点序号 101int nmixcost = INFINITE; 102 103tcost = (int*)malloc(g_node_num * sizeof(int)); 104pbDone = (BOOL*)malloc(g_node_num * sizeof(BOOL)); 105if(NULL == tcost || NULL == pbDone) { 106printf("out of memory\n"); 107return FALSE; 108} 109for(i=0; arr[i].pVer!=0; i++) {//依次将每个顶点作为起始节点 110for(j=0; jnext = (vertex**)malloc(g_node_num * sizeof(vertex*)); //储存每个顶点最优的前驱顶点的id的数组 116pbegin->pmincost = (int*)malloc(g_node_num * sizeof(int)); //储存每个顶点到起始顶点的最小代价数组 117tcost[i] = 0; //初始化 118pbDone[i] = 1; 119pbegin->pmincost[i] = 0; 120ptemp = pbegin; //设定起始顶点为当前顶点 121 122while(1) { 123for(j=0; ptemp->pLinkList[j]!=0; j++) {//遍历当前顶点的相邻节点，更新最小代价(松弛边) 124ptemp1 = ptemp->pLinkList[j]; 125if(tcost[ptemp1->id-1] > tcost[ptemp->id-1] + ptemp->nCost[ptemp1->id-1] \ 126&& pbDone[ptemp1->id-1] == 0) { 127tcost[ptemp1->id-1] = tcost[ptemp->id-1] + ptemp->nCost[ptemp1->id-1]; 128pbegin->next[ptemp1->id-1] = ptemp; //设定顶点更新后的前驱顶点 129} 130} 131nmixcost = INFINITE; 132for(j=0; jpmincost[nidtemp-1] = nmixcost; 142ptemp = arr[nidtemp-1].pVer; //重新设定当前顶点 143pbDone[nidtemp-1] = 1; //表示当前顶点已经被处理过了，其路径已经最短，代价最小 144} 145} 146free(pbDone); 147free(tcost); 148return TRUE; 149 } 150 /********************************************************** 151 *函数名：MinRoute 152 *参数：arr-图的数组；nSrID-起始节点序号；nDsID-目的节点序号 153 *返回值：无 154 *说明：给定图的数组，利用Dijkstra函数处理之后，根据设定的起始和终止节点序号，打印 155 *最短路径和最小代价。 156 ***********************************************************/ 157 void MinRoute(node arr[], UINT nSrID, UINT nDsID) 158 { 159if(nSrID<0 || nSrID>g_node_num || nDsID<0 || nDsID>g_node_num) { 160printf("Invalid node number!\n"); 161} 162int nid; 163vertex *ptemp = arr[nSrID-1].pVer; 164printf("the total cost is: %d\n", ptemp->pmincost[nDsID-1]); 165printf("the path is:"); 166nid = nDsID; 167printf("%d->",arr[nid-1].nID); 168while(ptemp->next[nid-1]->id != arr[nSrID-1].nID) { 169nid = ptemp->next[nid-1]->id; //回溯路径 170printf("%d->",nid); 171} 172printf("%d\n",arr[nSrID-1]); 173 } 174 /***************************************** 175 *函数名：UnitGraphic 176 *参数：arr-图的数组 177 *返回值：无 178 *说明：释放内存 179 *****************************************/ 180 void UnitGraphic(node arr[]) 181 { 182UINT i; 183for(i=0; inext); 186SAFEFREE(arr[i].pVer->pmincost); 187} 188} 189 }

文章图片

文章图片
main.c

1 #include 2 #include 3 #include 4 #include "Dijkstra.h" 5 6 int main(int argc, char *argv[]) 7 { 8char filepath[MAX_STRLEN]; //图的信息文件 9node graphic[MAX_VERTEX_NUM] = {0}; //图的数组 10int sid, did; 11int selnum; 12 13if(argc < 2) { 14printf("usage:*.exe input\n"); 15exit(1); 16} 17strcpy(filepath, argv[1]); 18/***********初始化图***************/ 19if(!InitGraphic(filepath, graphic, MAX_VERTEX_NUM)) { 20UnitGraphic(graphic); 21exit(1); 22} 23printf("****Print The Graphic information****"); 24ViewGraphic(graphic); //打印图 25/************dijkstra运算***********/ 26if(!Dijkstra(graphic)) { 27UnitGraphic(graphic); 28exit(1); 29} 30 31printf("\n****Find the shortest path between nodes****"); 32printf("\n1.View minimum route between nodes."); 33printf("\n2.Exit."); 34 35for(; ; ) { 36printf("\nEnter Your Selection:"); 37scanf("%d",&selnum); 38switch(selnum){ 39case 1:{ 40printf("\nEnter source node ID:"); 41scanf("%d",&sid); 42printf("\nEnter destination node ID:"); 43scanf("%d",&did); 44 45MinRoute(graphic, sid, did); //打印最优路径 46break; 47} 48case 2: 49exit(1); 50default: { 51printf("\nEnter proper choice.\n"); 52break; 53} 54} 55} 56UnitGraphic(graphic); 57return 0; 58 }

demo:
输入文件内容：

1:2-2:3-4:5-4; 2:1-2:3-3; 3:1-4:2-3:5-6:6-7; 4:6-8; 5:1-4:3-6; 6:3-7:4-8;

格式说明：
起始节点：连接节点1-权值：连接节点2-权值：连接节点3-权值.....
图的结构：

文章图片

运行结果：

文章图片


三：总结
Dijkstra最短路径搜索属于广度优先搜索(BFS, Breadth-First-Search)，即不断去搜索当前节点的所有相邻节点，并更新它们的cost。更新的前提是认为：当前节点是目前与起始节点之间cost最小的节点，它认为自己是最优解，要想到达目的节点，经过我这里必然错不了，接着在此基础上不断去寻找其它最优路径，运用的是一种贪婪算法的思想。但是有时候并不是最优解，典型的例子就是：最小数目找零的例子，现有10元，5元，1元的纸币，如果要找15块钱，贪婪算法的结果是-10元+5元。但是如果现在假设银行发行了12元一张的纸币(银行闲的蛋疼)，还用贪婪算法，结果是12+1+1+1(坑爹的，找这么多硬币！！)。但是实际上最优解仍然是10元+5元。所以有时候，具体问题要具体分析。另外，最优路径搜素还有带有启发性的A*搜索，双向广度优先搜索(BFS），它们比Dijkstra算法的搜索效率要高。改天再续。
再说一下，我的代码中，在寻找下一个当前节点时，用了全局搜索，这显然是一个很笨的方法，复杂度太高。一般的方法都是定义一个开集，一个闭集，用来存储未处理过的节点和已被处理的节点，所以我们可以用FIFO队列去优化。参考资料1。

参考资料：
1，《数据结构与算法分析-c++描述》,weiss
2，http://en.wikipedia.org/wiki/Dijkstra's_algorithm
3，http://blog.chinaunix.net/uid-20662820-id-142445.html
4，http://www.rawbytes.com/dijkstras-algorithm-in-c/

转载于:https://www.cnblogs.com/wb-DarkHorse/archive/2013/03/12/2948467.html

推荐阅读

• 

  有没有什么好看的情侣头像,最好是酷酷哒？
• 

  微信群主能删除成员发的信息吗
• 

  跨境电商运营是做什么的 不做电商平台做什么，个人如何做电商
• 

  俄顷怎么读 茅屋为秋风所破歌俄顷怎么读
• 

  redis缓存如何实现 redis缓存电子书
• 

  丰田双擎质量可靠吗 丰田雷凌双擎怎么样
• 

  干鱿鱼做法 希望可以帮助到有需要的朋友
• 

  老人高血压？五款保健茶能有效对抗高血压
• 

  青鳉鱼怎么养
• 

  菱叶
• 

  网上贷款有哪些途径安全吗？了解一下网上贷款常见骗局！
• 

  鸡胸肉柴了怎么补救
• 

  跨境电商是做什么的 在广州做电商有什么条件，电商是什么怎么做
• 

  羊角蜜和火龙果能一起同吃吗
• 

  减肥可以长期吃茯苓吗
• 

  脸上天天抹芦荟胶好不好
• 

  厦门作为国内拍摄婚纱照的圣地，在厦门拍婚纱照需要多少钱呢？
• 

  历史上第一个太监叫什么名字 中国历史上第一个太监是谁
• 

  玻璃|前后纳米微晶玻璃 抗跌能力提升5倍！华为P50 Pro典藏版正式开售
• 

  《魔偶马戏团》这部十月新番值得看吗？其豆瓣8.9分会不会虚高？

• 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
• 普通人通往大神的3个创作路径
• C#|C# 文件路径操作
• 最短且最痛心的恋爱
• 实践心得（产品高效实践MVP模型的路径）
• 思科路由映射表控制BGP路径的方法和实例
• 商业变现永不眠|商业变现永不眠(一) — 什么是决定商业化路径的底层逻辑（）
• Create|Create React app 引用中使用绝对路径
• 两点之间直线最短，但不一定最快
• 2018-12-04MAC怎么获取文件路径