东北大学计算机专业算法设计与分析课件

#include <stdio.h> int c[11][11] = {{2000,1,4,4,2000,2000,2000,2000,2000,2000,2000}, {2000,2000,4,2000,1,4,2000,2000,2000,2000,2000}, {2000,2000,2000,2000,2000,1,1,2000,2000,2000,2000}, {2000,2000,2000,2000,2000,2000,1,2000,2000,2000,2000}, {2000,2000,2000,2000,2000,2000,2000,1,4,2000,2000}, {2000,2000,2000,2000,2000,2000,4,2000,4,2000,2000}, {2000,2000,2000,2000,2000,2000,2000,2000,4,4,2000}, {2000,2000,2000,2000,2000,2000,2000,2000,2000,2000,1}, {2000,2000,2000,2000,2000,2000,2000,2000,2000,2000,4}, {2000,2000,2000,2000,2000,2000,2000,2000,4,2000,4}, {2000,2000,2000,2000,2000,2000,2000,2000,2000,2000,2000}};//2000标识无直接通路 const int maxdot=11; int dist[maxdot]; int previous[maxdot]; //record the directly previous node void ShortPaths(int v,int c[maxdot][maxdot],int n)//找从v到n的最短路径 { int i,j; bool s[maxdot]; int p[maxdot][maxdot]; for(i=1;i<=n;i++) { dist[i]=c[v][i]; //距离 previous[i]=v; //保留节点顺序，初始化各节点的前一个节点均为v s[i]=false; //未走过该节点 } dist[v]=0; //和本身的距离为0 s[v]=true; //标识最短路线是和本身 for(i=1;i<n;i++) { int temp=1000; //随便设置一个权 int u=v; //设定和v最短的是本身 for(j=1;j<=n;j++) { if(!s[j]&&(dist[j]<temp)) //s[j] 为标识有无连线,标识v和j之间有连线,第一次执行时五连线的为2000，进不来 { u=j; //当前j和v最近 temp=dist[j];//保存最短的值,更新temp值 } } s[u]=true;//找到了和v节点最近的节点u,标识走过了u节点 //剪枝 for(j=1;j<=n;j++)//之所以j从1开始，是因为没有和0节点反向连线的 { if(!s[j]&&(c[u][j]<1000)) //未走过，且u和j间有通路 { int newdist=dist[u]+c[u][j];//dist中存放和v节点连线的所有节点间的距离，而dist[u]标识v和最优节点u之间的距离 if(newdist<dist[j])//v和j之间没连接时，长度定为2000，也符合 { dist[j]=newdist;//更新从v到j的最短距离并注明路径 previous[j]=u; //update the directly previous node } } } } } void find(int v,int u) // 'v' here must be identical with the 'v' in above function { //output the path in reverse order while(u!=previous[u]) //有路径 { u=previous[u]; // retrieve the previous node printf("%d\n",u); } } void main() { ShortPaths(2,c,10); find(2,10) ; }