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];
        }
    }

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

//可打印最短路路径
#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;
}