[图算法]Dijkstra算法(附随笔[迟到的程序])
Dijkstra是由荷兰算法学家Edgar Wybe Dijkstra于60年代初期提出的一个关于图的最小路径的算法,经典而小巧.
主要的算法描述是这样的
L(x)标示由结点a到结点x的长度,算法结束时,L(z)表示的是从a到z的最短长度 .
Prodedure Dijkstra (G:所有权都为正数的加权连通简单图)
{G带有顶点a=v0,v1,…,vn-1,vn=z和权w(vi,vj),若{vi,vj}不是G中的边,则w(vi,vj)=无穷大}
For i:=1 to n
L(vi):=无穷大
L(a):=0
S:=空集
{初始化标记:a的标记为0,其余结点标记为无穷大,程序中可以用一个很大的整数代替,S是空集}
While z不属于S
Begin
U:=不属于S的L(u)最小的一个顶点
S:=S并上{u}
For 所有不属于S的顶点v
If(L(u)+w(u,v)<L(v))
Then L(v):=L(u)+w(u,v)
{这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记}
End{L(z)=从a到z的最短路的长度}
通常实现时,
1)要用到字典来存结果,我这里仅通过输出结果做简单处理.
2)本来通常在这个算法里用的优先队列也改用一个结构体矩阵简化代替.
/* Dijkstra算法(简单数据类型实现)
Made by EmilMatthew
05/8/10
*/
#include "Global.h"
#include <stdio.h>
#ifndef DijkstraAlgorithm_H
#define DijkstraAlgorithm_H
typedef struct
{
int selected;
int l_u;/*Now Length From the Start Node*/
int id;
char name;
}dNode;
extern int minNodeUnSelected(dNode* myNode,int len);
extern void shortestLenAdjust(dNode *myNode,Type** wArr,int len,int u);/*shortest path length adjust*/
#endif
int minNodeUnSelected(dNode* myNode,int len)/*seleted the nearest node*/
{
int findFirst=0;
int currentMinIndex=0;
int i=0;/*iterator control*/
assertF(myNode!=NULL,"in minNodeUnSelected ,myNode is null\n");
for(i=0;i<len;i++)
{
if(!myNode[i].selected)
{
/*Core Idea*/
/*
if L(u)+w(u,v)<L(v) then
L(v)=L(u)+w(u,v)
*/
if(!findFirst)
{
findFirst=1;
currentMinIndex=i;
}
else
{
if(myNode[i].l_u<myNode[currentMinIndex].l_u)
currentMinIndex=i;
}
}
}
assertF(findFirst==1,"in minNodeUnSelected ,findFirst is null\n");
myNode[currentMinIndex].selected=1;
return currentMinIndex;
}
void shortestLenAdjust(dNode *myNode,Type** wArr,int len,int u)/*shortest path length adjust*/
{
int v=0;/*iterator num*/
assertF(myNode!=NULL,"in shortestLenAdjust,myNode is NULL\n");
assertF(wArr!=NULL,"in minNodeUnSelected ,wArr is null\n");
for(v=0;v<len;v++)
{
if(!myNode[v].selected)
{
/*core idea*/
if(myNode[u].l_u+wArr[u][v]<myNode[v].l_u)
myNode[v].l_u=myNode[u].l_u+wArr[u][v];
}
}
}
/*Dijkstra Algorithm test program*/
#include "Global.h"
#include "Ulti.h"
#include "SortAlgorithm.h"
#include "DijkstraAlgorithm.h"
#include "MyAssert.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *inFileName="inputData.txt";
/*
input data specification
row,col,
startNodeId,endNodeId,should obey the rule in C Language.Start from 0
wArr
{
, , , ,
, , , ,
, , , ,
}
*/
char *outFileName="outputData.txt";
#define DEBUG 1
void main(int argc,char* argv[])
{
FILE *inputFile;/*input file*/
FILE *outputFile;/*output file*/
double startTime,endTime,tweenTime;/*time callopsed info*/
int row,col;
Type** wArr;
int i,j;/*iterator index*/
int n;/*arr deminision for squre matrix*/
char* ansList;/*the answer list to get the shortest path info*/
int curAnsCharLen;/*the len of the ansList char* */
int u;/*The temp nearest node id*/
int startNodeId,endNodeId;/*the start and end node location*/
dNode* myNode;
int tmpLen;/*temp data*/
int posAdjust=0;
/*input file open*/
if(argc>1)strcpy(inFileName,argv[1]);
assertF((inputFile=fopen(inFileName,"rb"))!=NULL,"input file error");
printf("input file open success\n");
/*outpout file open*/
if(argc>2)strcpy(outFileName,argv[2]);
assertF((outputFile=fopen(outFileName,"wb"))!=NULL,"output file error");
printf("output file open success\n");
/*start data read in*/
fscanf(inputFile,"%d,%d,",&row,&col);
fscanf(inputFile,"%d,%d,",&startNodeId,&endNodeId);
/*****************data init*****************/
/****argu prepare****/
assertF(col==row,"in test col!=row");
n=row;/*get the size of square matrix*/
/*myNode memory apply*/
myNode=(dNode*)malloc(sizeof(dNode)*n);
for(i=0;i<n;i++)
{
myNode[i].selected=0;
myNode[i].id=i;
myNode[i].l_u=IntLimit;
}
ansList=(char*)malloc(sizeof(char)*n*4);/*only could tackle with gLen<100*/
/*clean the rubbish strings*/
tmpLen=sizeof(char)*n*4;
for(i=0;i<tmpLen;i++)
{
ansList[i]='\0';
}
/*************end of data init******************/
/*Memory Apply*/
wArr=(Type**)malloc(sizeof(Type*)*row);
for(i=0;i<row;i++)
wArr[i]=(Type*)malloc(sizeof(Type)*col);
/*Read 2d arr data*/
for(i=0;i<row;i++)
{
for(j=0;j<col-1;j++)
fscanf(inputFile,"%d,",&wArr[i][j]);
fscanf(inputFile,"%d;",&wArr[i][j]);
}
/*big length adjust*/
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(wArr[i][j]==-1)wArr[i][j]=IntLimit;
show2DArr(wArr,row,col);
#if DEBUG
printf("\n*******start of test program******\n");
printf("now is runnig,please wait...\n");
startTime=(double)clock()/(double)CLOCKS_PER_SEC;
/******************Core program code*************/
curAnsCharLen=0;/*the set of the answer should be empty*/
myNode[startNodeId].l_u=0;
fprintf(outputFile,"The shortest path's node sequence using dijkstra algorithm in this Graph is:\r\n");
while(!myNode[endNodeId].selected)
{
u=minNodeUnSelected(myNode,n);/*seleted the nearest node*/
//addToAnsList(ansList,&curAnsCharPos,u);/*add it to the answer list*/
/*output the shortest path*/
fprintf(outputFile,"%d,",u);
if(posAdjust++>10)
{
posAdjust=0;
fprintf(outputFile,"%\r\n");
}
shortestLenAdjust(myNode,wArr,n,u);/*shortest path length adjust*/
}
fprintf(outputFile,"\r\nThe shortest path's lenth in this Graph is:%d\r\n",myNode[endNodeId].l_u);
/******************End of Core program**********/
endTime=(double)clock()/(double)CLOCKS_PER_SEC;
tweenTime=endTime-startTime;/*Get the time collapsed*/
/*Time collapsed output*/
printf("the collapsed time in this algorithm implement is:%f\n",tweenTime);
fprintf(outputFile,"the collapsed time in this algorithm implement is:%f\r\n",tweenTime);
printf("\n*******end of test program******\n");
#endif
/*Memory Free out*/
for(i=0;i<row;i++)
free(wArr[i]);
free(wArr);
printf("program end successfully,\n you have to preess any key to clean the buffer area to output,otherwise,you wiil not get the total answer.\n");
getchar();/*Screen Delay Control*/
return;
}
//测试结果:
//Inputdata
6,6,
0,5,
0,4,2,-1,-1,-1;
4,0,1,5,-1,-1;
2,1,0,8,10,-1;
-1,5,8,0,2,6;
-1,-1,10,2,0,3;
-1,-1,-1,6,3,0;
//OutpoutData
The shortest path's node sequence using dijkstra algorithm in this Graph is:
0,2,1,3,4,5,
The shortest path's lenth in this Graph is:13
the collapsed time in this algorithm implement is:0.000000
Washall,Floyd,Dijkstra三个图算法的源码下载:
http://emilmatthew.51.net/downloads/GraphAlgorithm.rar
（直接点击地址栏可能会下不下来，请单击右键，用"另存为"或用下载软件软件下载）
=====================================================================
附:随笔-----<迟到的程序>
第一次看到Edgar Wybe Dijkstra这个名字是在今年三月份我在读一本关于程序设计方法学的书,当时看见的他的事迹是”高声喊不要在程序里使用goto”.由于我学的语言还算”现代”,所以我基本没在自己的程序里用过goto,但是我还是被这个人的名字所吸引,这个人究竟做了些什么大事,讲这么一句话就可以让那么多人记住.
从那时起,我开始有意识的了解关于我们计算科学专业一些比较严肃的书籍(基本没有程序设计语言的),我知到了谁是高德纳,谁是艾伦.凯,什么是容错系统…当然,也把Edgar Wybe Dijkstra的事迹牢记于心.我开始真正的清楚了解什么才是Computer Science.也开始重新定位了自己的人生道路,这里就不细讲了.
想领略大师的风采请点这里:(我经心整理的)
http://free5.e-168.cn/hhucskx/computerScience/scientistIndex0.htm
说计算机教育落后,说过时,那都是相对的,如果要学新技术,你永远是落后的.这并不是说技术不重要,而是现在程序界几乎就是技术的天下(以JAVA和.Net为代表).海归美藉华人周怀北博士说过:”技术这个东西,大家都知道,有时就像一层纸,一捅就破,今天你会是比别人做的好些,但慢慢地别人也会熟悉,多翻翻书,多看看,多钻研一下,细节是可以搞清楚的.”这不是说技术不重要,而是说,现在对技术的痴迷程度,已到了登峰造级的程度.原因,我理解的,用流行的话来讲,就是:来钱容易,学起来也容易.学技术的人当然要有,但太多了,心态就难免浮躁,思考一些事情也就难免偏激了.
谭浩强老师说过:”现在有的学生说C语言不好,要学C++.我就是弄不明白,难道C语言在中国真的过时了,我不这样认为.C语言是基础,学好了它,再学C++就不难了”.这一点,我自己现在是深有体会的.我虽然会五种编程语言(VB,C,C++,JAVA,ActionScript)但除去ActionScript外,我基本上就没有称得上算精通的语言了.最近开始攻算法时,与C语言刚刚进行了些稍微亲密的接触,才真正对这种语言有了些初步深入的体会.
想了解对计算机科学的理性思考请点这里:
http://free5.e-168.cn/hhucskx/computerScience/sourceList0.htm
“计算机科学,说到底,就是算法的科学.----高德纳”这句话,即使是在今天,也一点不算过份份.而我想补充的是:在计算机科学的任何一个方面,如果你想要做深入的理解,如果没有数学等传统科学(包括文科的)的理性思考,又怎么可能实现呢?UML及Design Patterns之所以得到的大家的认可和广泛的应用,那就是因为他们的创造者有能力将一些看似由经验支撑的东西加以形式化的表述;宇航飞机的代码有几百万行,有BUG是必然的,如何构造一个好的容错系统,就不是几个测试程序能搞定的了,必须有严格有效的数学方法加以辅助; Dijkstra,Wasall这样的算法,如果少了数学的证明,根本就不可能被学术界认可;操作系统间资源的优化调度,本身就是相当复杂的数学优化问题……所以,你可以看到,著名的计算机科学家,同时也是一个数学家(至少是应用数学方面的确的).刚开始学编程的时候,你会觉得这里的思考方式和以往的学科有些不一样,但学着学着,尤其是多接解了计算机科学本身的一些话题后,你就会越来越清楚的感受到,这里所蕴含的智慧,和所有的学科都是想通的.(当然,我还没有这样的境界)
我不想再做太多点评了,二三两段所引用这些话已代表了我的观点.程序界的谩骂我已经有所领教,自然要小心点了.我只想再点评一句话,如果你真的想做些研究,想做些有深度的东西的话,请珍惜你在大学里的每一天,无论你在怎样的一所大学,想要学习的话,总是可以的,关键在于你自己怎么想.而且也无论你学什么东西,都要认真对待,如果你认为自己学软件的就可以不必学硬件类的课程了,那就危险了,因为这种实用主义最终将会使你知识体系陷入一个很狭隘的范围(这样的话,干脆去读外面的培训班好了).读大学这四年间所积累下的你的实力和底蕴,是你今后一生奋斗的动力与基石.不要在大学里呆四年花钱买个教训,以后跑到社会上,后悔自己当年为什么不多学点.因为在大学里,学习是俯抬即是的东西,以后再要补,心态和环境就完全的不一样的.而且,当你大学养成了一个好的自学习惯后,可以使你以后无论何时何地都能有更进一步的提高,除非你真的觉得学习不那么重要.(当然,不排除被中国教育制度毒害的因素)
最后,言归正传, 为什么这篇文章的题目叫做<迟到的程序>的呢?因为我作为一个即将升入大三的计算机专业的学生,到大二的暑假才刚将Dijkstra算法实践了一下,实在应该做检讨,打板子.其实这个程序,我期待亲手实践它有长时间了.今天,当我在键盘上敲下这个程序的最后几个代码的时候,我的心情是异常激动的,眼眶中竟不自觉得泛着泪光,因为这是我在计算机科学道路上的又一个值得纪念的聚点..当我看到程序实现的效果时,再一次被它的精致和美妙所折服,体会到什么才叫”The art of compouter program”.沿着大师们走过的足迹,我的心中坦荡无比……
社会在变,人的心态也在变,但把握住其中一些不变的,一些纯朴而又永恒的真理(如理想,奋斗,自信,毅力等),你的人生就不会偏失方向
我,回归理性,回归科学,自信在计算机科学这条路上走得更好……
与所有理性思考自己人生并为自己的人生目标奋斗的朋友共勉!
