dijkstra

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

1) 首先我们定义 


struct map{　　　　　　 


 int num;　　　　　　　 //存放结点数 


 int weight[30][30];} g;　//存放结点之间的权重 


int *d;　//用d[i]表示结点i到源结点的最短路径的总权重 


int *r;　//用r[i]表示最短路径中i的前一个结点 


用上面的类型存放图的信息 




2)然后定义一个函数（也是程序的核心） 


void shortpath(){　　  //计算最短路径 


 int final[30];　　　  //当结点I到源结点的最短路径被算出后final[i]=true； 


//表示结点被删除 


 int min; 


 int w,v; 


 int v0=1; //起始结点 


 int i; 


 for(v=1;v<=g.num;++v){　　//初始化 


　final[v]=false; 


　d[v]=g.weight[v0][v]; 


　if(d[v]<max)r[v]=v0; 


　} 




  d[v0]=0;final[v0]=true;　　　 //删除源结点 




　for(i=1;i<=g.num;++i){ 


　min=max; 




　　for(w=1;w<g.num;++w){　//选择最小的d[ ] 


　　　if(!final[w]) 


　　　  if(d[w]<min){v=w;min=d[w];} 


　　}/ 


final[v]=true ;　　 //删除结点v 


for(w=1;w<=g.num;++w){　 //最短路径的选择 


if(!final[w] && min+g.weight[v][w]<d[w]){ 


　d[w]=min+g.weight[v][w]; 


　r[w]=v;} 


　　　　　　　　　　　 } 


} 


　　　 } 


3）编写main（）主函数 


 main(){ 


scanf(图片信息) 


shortpath（）　//调用2）中的函数 


printf(输出需要的路径信息 


} 


这部分不是主要部分，也比较简单，所以请读者自行添加。 


再次强调步骤2）是程序的核心，真个算法包含其中，需要研究体会。