对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

下面给出代码：

void Dijkstra(MGraph &g,int vex)   //迪杰斯特拉算法 { int visit[MAXVEXNUM];  //记录顶点是否访问 int i,j; //初始化 for(i=0;i<g.n;i++) {   visit[i] = 0; if(g.edges[vex][i] == INFINITY)    prev[i] = -1;  //prev[i]为第i个顶点的前一个顶点   else    prev[i] = vex; } visit[vex] = 1; for(i=1;i<g.n;i++) {   int tmp = INFINITY;   int u = vex;   for(j=0;j<g.n; j++)   //找最短路径   {    if(!visit[j] && g.edges[vex][j] < tmp)    {       u = j;       tmp = g.edges[vex][j];    }   }   visit[u] = 1;   for(j=0;j<g.n;j++)   //通过最短路径依次找次短路径   {    if(!visit[j] && g.edges[u][j] < INFINITY)    {     int newdist = tmp + g.edges[u][j];     if(newdist < g.edges[vex][j])     {      g.edges[vex][j] = newdist;      prev[j] = u;     }    }   } } }

void Floyd(MGraph &g,int p[MAXVEXNUM][MAXVEXNUM][MAXVEXNUM])    //弗洛伊德算法

{ int u, v, w, i, j; //初始化 for(v=0; v<g.n; v++)   for(w=0; w<g.n; w++)   {    for(u=0; u<g.n;u++)     p[v][w][u]=-1;   //p为存储路径    if(g.edges[v][w] < INFINITY)    {     p[v][w][0]=v;     p[v][w][1]=w;    }   }     for(u=0; u<g.n; u++)    for(v=0; v<g.n; v++)     for(w=0; w<g.n; w++)      if(g.edges[v][u]+g.edges[u][w] < g.edges[v][w])      {       g.edges[v][w] = g.edges[v][u]+g.edges[u][w];       //更新p，从v到w的路径是从v到u，再从u到w的所有路径       for(i=0; i<g.n; i++)       {        if(p[v][u][i]!=-1)         p[v][w][i]=p[v][u][i];        else         break;       }       for(j=1; j<g.n; j++)//注意：这里j从1开始而不是从0开始，因为从v到u的路径最后一个顶点是u, 而从u到w的路径第一个顶点是u，只需打印u一次即可。       {        if(p[u][w][j]!=-1)         p[v][w][i++]=p[u][w][j];        else         break;       }            }

}