最短路径：Dijkstra，Bellman，SPFA，Floyd算法的实现

</pre><pre name="code" class="cpp">



#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

const int INF = 0x3f3f3f3f;//无穷大
const int maxn = 20;//顶点个数的最大值
int n;//顶点个数
int edge[maxn][maxn];//邻接矩阵
//Dijkstra算法用到的3个数组
int s[maxn];//记录顶点是否在集合中
int dist[maxn];//记录路径的权值
int path[maxn];//记录路径

void Dijkstra( int v0 )//求v0到其他点的最短路径
{
    int i, j, k;//循环变量
    for(i=0; i<n; i++)
    {
        dist[i] = edge[v0][i];
        s[i] = 0;
        if( i!=v0 && dist[i]<INF )
            path[i] = v0;
        else
            path[i] = -1;
    }
    s[v0] = 1; dist[v0] = 0;//顶点v0加入顶点集合s
    for(i=0; i<n-1; i++)//从顶点v0确定n-1条最短路径
    {
        int min = INF, u = v0;
        //选择当前集合T中具有最短路径的顶点u
        for(j=0; j<n; j++)
        {
            if( !s[j] && dist[j]<min )
            {
                u = j;
                min = dist[j];
            }
        }
        s[u] = 1;//将顶点u加入集合s，表示它的最短路径已求得
        //修改T集合中顶点的dist和path数组元素
        for(k=0; k<n; k++)
        {
            if( !s[k] && edge[u][k]<INF && dist[u]+edge[u][k]<dist[k] )
                {
                    dist[k] = dist[u] + edge[u][k];
                    path[k] = u;
                }
        }
    }
}

int main()
{
    int i, j;//循环变量
    int u, v, w;//边的起点和终点以及权值
    scanf("%d", &n);//读入顶点个数n
    while(1)
    {
        scanf("%d%d%d", &u, &v, &w);
        if( u==-1 && v==-1 && w==-1 )
            break;
        edge[u][v] = w;//构建邻接矩阵
    }
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            if( i==j )
                edge[i][j] = 0;
            else if( edge[i][j] == 0 )
                edge[i][j] = INF;
        }
    }
    Dijkstra(0);//求顶点0到其他顶点的最短路径
    int shortest[maxn];//输出最短路径上的各个顶点时存放各个顶点的序号
    for(i=1; i<n; i++)
    {
        printf("%d\t", dist[i]);//输出顶点0到顶点i的最短路径长度
        //以下代码用于输出顶点0带顶点i的最短路径
        memset( shortest, 0, sizeof(shortest) );
        int k = 0;//k表示shorttest数组中最后一个元素的下标
        shortest[k] = i;
        while( path[ shortest[k] ]!=0 )
        {
            k++;
            shortest[k] = path[shortest[k-1]];
            //printf("%d ", k);
        }
        k++; shortest[k] = 0;
        //printf("%d", k);
        for(j=k; j>0; j--)
            printf("%d--", shortest[j]);
        printf("%d\n", shortest[0]);
    }

    return 0;
}
           

Bellman：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 8;
int edge[maxn][maxn];
int dist[maxn];
int path[maxn];
int n;

void Bellman(int v0)
{
    int i, j, k, u;
    for(i=0; i<n; i++)
    {
        dist[i] = edge[v0][i];
        if( i!=v0 && dist[i] < INF )
            path[i] = v0;
        else
            path[i] = -1;
    }
    for(k=2; k<n; k++)
    {
        for(u=0; u<n; u++)
        {
            if( u!=v0 )
            {
                for( j=0; j<n; j++ )
                {
                    if( edge[j][u] < INF && dist[j] + edge[j][u] < dist[u] )
                    {
                        dist[u] = dist[j] + edge[j][u];
                        path[u] = j;
                    }
                }
            }
        }
    }
}

int main()
{
    int i, j;
    int u, v, w;
    scanf("%d", &n);
    while( 1 )
    {
         scanf("%d%d%d", &u, &v, &w);
         if( u==-1 && v==-1 && w==-1 )
            break;
         edge[u][v] = w;
    }
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            if( i==j )
                edge[i][j] = 0;
            else if( edge[i][j]==0 )
                edge[i][j] = INF;
        }
    }
    Bellman(0);
    int shortest[maxn];
    for(i=1; i<n; i++)
    {
        printf("%d\t", dist[i]);
        memset( shortest, 0, sizeof(shortest) );
        int k = 0;
        shortest[k] = i;
        while( path[shortest[k]]!=0 )
        {
            k++;
            shortest[k] = path[shortest[k-1]];
        }
        k++;
        shortest[k] = 0;
        for(j=k; j>0; j--)
            printf("%d--", shortest[j]);
        printf("%d\n", shortest[0]);
    }

    return 0;
}
           

SPFA：

#include <cstdio>
#include <cstring>
#include <queue>
#define INF  1000000  //无穷大
#define MAXN 10

using namespace std;

struct ArcNode
{
    int to;
    int weight;
    struct ArcNode *next;
};

queue<int> Q;  //队列中的结点为顶点序号
int n;   //顶点个数
ArcNode* List[MAXN];  //每个顶点的边链表表头指针
int inq[MAXN];  //每个顶点是否在队列中的标志
int dist[MAXN];  //
int path[MAXN]; //

void SPFA( int src )
{
    int i, u;  //u为队列头顶点序号
    ArcNode* temp;
    for( i=0; i<n; i++ )  //初始化
    {
        dist[i] = INF;
        path[i] = src;
        inq[i] = 0;
    }
    dist[src] = 0;
    path[src] = src;
    inq[src]++;
    Q.push( src );
    while( !Q.empty() )
    {
        u = Q.front( );
        Q.pop( );
        inq[u]--;
        temp = List[u];
        while( temp!=NULL )
        {
            int v = temp->to;

            if( dist[v] > dist[u] + temp->weight )
            {
                dist[v] = dist[u] + temp->weight;
                path[v] = u;
                if( !inq[v] )
                {
                    Q.push(v);
                    inq[v]++;
                }
            }
            temp = temp->next;
        }
    }
}

int main( )
{
    int i, j;  //循环变量
    int u, v, w;  //边的起点和终点及权值
    scanf( "%d", &n );  //读入顶点个数n
    memset( List, 0, sizeof(List) );
    ArcNode* temp;
    while( 1 )
    {
        scanf( "%d%d%d", &u, &v, &w ); //读入边的起点和终点
        if( u==-1 && v==-1 && w==-1 )    break;
        temp = new ArcNode;
        //构造邻接表
        temp->to = v;
        temp->weight = w;
        temp->next = NULL;
        if( List[u]==NULL )    List[u] = temp;
        else
        {
            temp->next = List[u];
            List[u] = temp;
        }
    }
    SPFA( 0 ); //求顶点0到其他顶点的最短路径
    for( j=0; j<n; j++ )  //释放边链表上各边结点所占用的存储空间
    {
        temp = List[j];
        while( temp!=NULL )
        {
            List[j] = temp->next;
            delete temp;
            temp = List[j];
        }
    }

    int shortest[MAXN];  //输出最短路径上的各个顶点时存放各个顶点的序号
    for( i=1; i<n; i++ )
    {
        printf( "%d\t", dist[i] );  //输出顶点0到顶点i的最短路径长度
        //以下代码用于输出顶点0到顶点i的最短路径
        memset( shortest, 0, sizeof(shortest) );
        int k = 0;  //k表示shortest数组中最后一个元素的下标
        shortest[k] = i;
        while( path[ shortest[k] ] != 0 )
        {
            k++;
            shortest[k] = path[ shortest[k-1] ];
        }
        k++;
        shortest[k] = 0;
        for( j=k; j>0; j-- )
            printf( "%d→", shortest[j] );
        printf( "%d\n", shortest[0] );
    }
    return 0;
}
           

Floyd：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;
#define INF  1000000  //无穷大
#define MAXN 8

int n;   //顶点个数
int Edge[MAXN][MAXN];  //邻接矩阵
int A[MAXN][MAXN];    //
int path[MAXN][MAXN];  //

void Floyd( ) //假定图的邻接矩阵和顶点个数已经读进来了
{
    int i, j, k;
    for( i=0; i<n; i++ )
    {
        for( j=0; j<n; j++ )
        {
            A[i][j] = Edge[i][j]; //对a[ ][ ]初始化
            if( i!=j && A[i][j]<INF )    path[i][j] = i; //i到j有路径
            else path[i][j] = -1; //从i到j没有直接路径
        }
    }
//从A(-1)递推到A(0), A(1), ..., A(n-1),或者理解成依次将v0,v1,...,v(n-1)作为中间顶点
    for( k=0; k<n; k++ )
    {
        for( i=0; i<n; i++ )
        {
            for( j=0; j<n; j++ )
            {
                if( k==i || k==j )  continue;
                if( A[i][k] + A[k][j] < A[i][j] )
                {
                    A[i][j] = A[i][k] + A[k][j] ;
                    path[i][j] = path[k][j];
                }
            }
        }
    }
}

int main( )
{
    int i, j;  //循环变量
    int u, v, w;  //边的起点和终点及权值
    scanf( "%d", &n );  //读入顶点个数n
    for( i=0; i<n; i++ )  //设置邻接矩阵中每个元素的初始值为INF
    {
        for( j=0; j<n; j++ )    Edge[i][j] = INF;
    }
    for( i=0; i<n; i++ )  //设置邻接矩阵中对角线上的元素值为0
    {
        Edge[i][i] = 0;
    }
    while( 1 )
    {
        scanf( "%d%d%d", &u, &v, &w ); //读入边的起点和终点
        if( u==-1 && v==-1 && w==-1 )    break;
        Edge[u][v] = w; //构造邻接矩阵
    }
    Floyd( ); //求各对顶点间的最短路径
    int shortest[MAXN]; //输出最短路径上的各个顶点时存放各个顶点的序号
    for( i=0; i<n; i++ )
    {
        for( j=0; j<n; j++ )
        {
            if( i==j )  continue; //跳过
            printf( "%d=>%d\t%d\t", i, j, A[i][j] );  //输出顶点i到顶点j的最短路径长度
            //以下代码用于输出顶点0到顶点i的最短路径
            memset( shortest, 0, sizeof(shortest) );
            int k = 0; //k表示shortest数组中最后一个元素的下标
            shortest[k] = j;
            while( path[i][ shortest[k] ] != i )
            {
                k++;
                shortest[k] = path[i][ shortest[k-1] ];
            }
            k++;
            shortest[k] = i;
            for( int t=k; t>0; t-- )
                printf( "%d→", shortest[t] );
            printf( "%d\n", shortest[0] );
        }
    }

    return 0;
}