求单源最短路径（算法分析中）c++

#include <iostream> using namespace std; #define MAX 999 void getdata(int **c,int n) /*数据获取*/ { int i,j; int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; //对角线为0 else c[i][j]=MAX; //其它为最大值 }/*end for*/ }/*end for*/ do { cout<<"请输入 起点 终点 权值(-1退出)："; //数据的输入 cin>>begin; if(begin==-1) break; cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); // c[1][2]=10;c[1][4]=30;c[1][5]=100; // c[2][3]=50; c[3][5]=10;c[4][5]=60;c[4][3]=20; } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j]<temp)) {u=j;temp=dist[j];}//不在集合里，值《temp，选最小值 s[u]=true; for (j=1;j<=n;j++) { if((!s[j])&&(c[u][j]<MAX)) { int newdist=dist[u]+c[u][j]; if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}//前驱u记录下来 }/*end if*/ }/*end for*/ }/*end for*/ } void PrintPath(int *prev,int n,int begin,int end) { int *path=new int [n+1]; int i,m=n; bool k=true; path[end]=end; for(i=end-1;i>1;i--) { path[i]=prev[path[i+1]]; //构造路径 m--; } for (i=m;i<=end;i++) { cout<<path[i]<<"->"; //输出路径 } cout<<"\b\b"<<" "<<endl; } void main() { int n,i; int v=1; cout<<"请输入顶点个数："; cin>>n; int *dist=new int [n+1]; int *prev=new int [n+1]; int **c; c=new int *[n+1]; for (i=0;i<=n;i++) { c[i]=new int [n+1]; } getdata(c,n); //获取数据 int begin=1,end; cout<<"请输入所求单源路径的 起点 终点："; cin>>begin>>end; v=begin; Dijkstra(n,v,dist,prev,c); //计算路径 PrintPath(prev,n,begin,end); //输出路径 }