楼主

請問問Dijkstra問題 dijkstra怎麼可print出從一黠到另一點的路線，是要印出點，不是全部的weight值....     public static void Dijkstra(int vertex) {         int i, j;         int v = 0;         double minWeight;                  for (j=0;j<VertexNum;j++) {             smallestWeight[j] = weights[vertex][j];             weightFound[j] = false;         }                  smallestWeight[vertex] = 0;         weightFound[vertex] = true;                  for (i=0;i<VertexNum-1;i++) {             minWeight = Max;             for (j=0;j<VertexNum;j++)                 if (!weightFound[j])                     if (smallestWeight[j]<minWeight) {                         v = j;                         minWeight = smallestWeight[v];                     }                                  weightFound[v] = true;                          for (j=0;j<VertexNum;j++)                 if (!weightFound[j])                     if (minWeight + weights[v][j] < smallestWeight[j])                         smallestWeight[j] = minWeight + weights[v][j];         }     }    收藏   分享   顶(0)

	第2楼

设置一个数组来存储从源点最短路径上的当前目标点的前一点就应该可以的

	第3楼

我也试过这方面的,不过设置数组的时候,用CONST来确定就比较易,如果要求点(名称)和权值的输入就遇到麻烦,我到现在还实现不了.高手指教啦.

	第4楼

dijkstra是相对于固定原点的最短路算法，所以其中某一点到另一点的路不一定最短。 求这个源点到各点最短的路可以用一个数组表示，例如：L[]，它长为n，L[i]除记下到第i节点的最短路长度外，还可以加一个pre指针(结构实现)，pre用来记下到 i 这点的倒数第二点j，然后再查找L[j]的pre....直到找到源点，最后逆序输出就ok了。对于pre修改的过程可以在算法更新weight处进行，挺方便的。

	第5楼

看看这个对你有帮助没? //可打印最短路路径 #include "fstream.h" #include "string.h" ifstream fin("ural_1072.in"); const int MAX=1005; const int maxint=100000000; struct {  int n;  int q[MAX]; }inter[MAX]; int dis[MAX],g[MAX][MAX],marked[MAX],ans[MAX],from[MAX],from_floyd[MAX][MAX]; int n,s,t; void bellman_ford() {  int i,more,j,k,n_ans;  for (i=0; i<n; i++)   dis[i]=maxint;  dis[s]=0;  memset(from,-1,sizeof(from));  for (k=0; k<n+2; k++)  {   more=0;   for (i=0; i<n; i++)    if (dis[i]<maxint)     for (j=0; j<n; j++)      if (g[i][j] && dis[i]+g[i][j]<dis[j])      {       dis[j]=dis[i]+g[i][j];       from[j]=i;       more=1;      }      for (i=n-1; i>=0; i--)                             //反向松弛一遍    if (dis[i]<maxint)     for (j=0; j<n; j++)      if (g[i][j] && dis[i]+g[i][j]<dis[j])      {       dis[j]=dis[i]+g[i][j];       from[j]=i;       more=1;      }   if (!more)    break;  }  if (more)                                              //判负圈   cout<<"No shortest path!"<<endl;    if (dis[t]==maxint)  {   cout<<"No"<<endl;   return ;  }    cout<<"Yes"<<endl;  i=t;  n_ans=0;  do  {   ans[n_ans++]=i;   i=from[i];  }while (i!=-1);    for (i=n_ans-1; i>0; i--)   cout<<ans[i]<<' ';  cout<<ans[0]<<endl; }*/ void dijkstra() {  int i,k,j,minv,n_ans;  for (i=0; i<n; i++)   dis[i]=maxint;  dis[s]=0;  memset(marked,0,sizeof(marked));  memset(from,-1,sizeof(from));  k=s;  for (i=0; i<n; i++)  {   marked[k]=1;   for (j=0; j<n; j++)    if (!marked[j] && g[k][j] && dis[k]+g[k][j]<dis[j])    {     from[j]=k;     dis[j]=dis[k]+g[k][j];    }         minv=maxint;  for (j=0; j<n; j++)    if (!marked[j] && minv>dis[j])    {     minv=dis[j];     k=j;    }   if (minv==maxint)    break;  }  if (dis[t]==maxint)  {   cout<<"No"<<endl;   return ;  }  cout<<"Yes"<<endl;    i=t;  n_ans=0;  do  {   ans[n_ans++]=i;   i=from[i];  }while (i!=-1);   for (i=n_ans-1; i>0; i--)   cout<<ans[i]<<' ';  cout<<ans[0]<<endl;*/ } void printPath(int i,int j) {  if (from_floyd[i][j]==-1)  {   cout<<i<<' ';   return;  }  printPath(i,from_floyd[i][j]);  printPath(from_floyd[i][j],j); } void floyd() {  int i,j,k,n_ans;  memset(from_floyd,-1,sizeof(from_floyd));    for (k=0; k<n; k++)                           //g是01矩阵时，用位运算比较快   for (i=0; i<n; i++)    for (j=0; j<n; j++)    {     g[i][j] |= g[i][k] & g[k][j];           from_floyd[i][j]=k;    }                                for (k=0; k<n; k++)   for (i=0; i<n; i++)    if (g[i][k])     for (j=0; j<n; j++)      if (g[k][j] && (!g[i][j] || g[i][j]>g[i][k]+g[k][j]))      {       from_floyd[i][j]=k;       g[i][j]=g[i][k]+g[k][j];      }  if (!g[s][t])  {   cout<<"No"<<endl;   return ;  }  cout<<"Yes"<<endl;    printPath(s,t);  if (s!=t)   cout<<t<<endl;*/  } int main() {  int i,j;  fin>>n;  for (i=0; i<n; i++)   for (j=0; j<n; j++)    fin>>g[i][j];  fin>>s>>t;    bellman_ford();  dijkstra();  floyd();  return 0; }

----------------------------------------------
菜鸟一个，想要多学点算法，多认识点朋友