分享
 
 
 

[图算法]Dijkstra算法(附随笔[迟到的程序])

王朝other·作者佚名  2006-01-31
窄屏简体版  字體: |||超大  

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”.沿着大师们走过的足迹,我的心中坦荡无比……

社会在变,人的心态也在变,但把握住其中一些不变的,一些纯朴而又永恒的真理(如理想,奋斗,自信,毅力等),你的人生就不会偏失方向

我,回归理性,回归科学,自信在计算机科学这条路上走得更好……

与所有理性思考自己人生并为自己的人生目标奋斗的朋友共勉!

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有