最短路径算法模板集合

Prim算法 适用于稠密图，时间复杂度O(n^2)

int Prim()
{
    int i,j,v,tmp,ans=0;
    for(i=1;i<=n;i++)
        dis[i]=inf;        //初始化
    dis[1]=0;
    for(i=1;i<=n;i++)
    {
        tmp=inf;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&tmp>dis[j])
            {
                tmp=dis[j];
                v=j;
            }         //找出最小距离的节点
        }
        vis[v]=1;     //把访问的节点做标记
        ans+=tmp;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>map[v][j])
                dis[j]=map[v][j];   //更新最短距离
        }  
    }  
    return ans;
}

Dijstra算法 适用于稀疏图，求单源、无负权的最短路。时效性较好，时间复杂度为O(nlogn)

void dijkstra()
{
    int i,j,v,min;
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    for(i=0;i<=n;i++)
    {
        dis[i]=map[0][i];
    }
    for(i=1;i<n;i++)
    {
        min=INF;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<min)
            {
                min=dis[j];
                v=j;
            }
        }
        vis[v]=1;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>dis[v]+map[v][j])
                dis[j]=dis[v]+map[v][j];
        }
    }
}

Floyd算法  求多源、有负权边的最短路。时间复杂度O(n^3）适用数据范围不大于500

void floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                    map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}