首页 > 代码库 > 最短路模版 (dijkstra&&flody)

最短路模版 (dijkstra&&flody)

1.dijkstra

void dijkstra(int x,int n)//x表示起点,n表示一共的数量{    int min=0,p=0;    for(int i=1;i<=n;i++)    {        dis[i]=map[x][i];        visited[i]=0;    }    visited[x]=1;    for(int i=1;i<=n;i++)    {        min=inf;        for(int j=1;j<=n;j++)        {            if(!visited[j]&&dis[j]<min)            {                min=dis[j];                p=j;            }        }        visited[p]=1;        for(int j=1;j<=n;j++)        {            if(!visited[j]&&dis[j]>dis[p]+map[p][j])                dis[j]=dis[p]+map[p][j];        }    }}

2.flody

void floyd(){    int i,j,k;    for(k=0;k<n;k++)        for(i=0;i<n;i++)            for(j=0;j<n;j++)                if(dis[i][j]>dis[i][k]+dis[k][j])                   dis[i][j]=dis[i][k]+dis[k][j];}

个人建议如果在能用dijkstra的地方就尽量用,flody一般会超时。当然如果遇负环的情况的时候就需要用spfa的算法了。 

最短路模版 (dijkstra&&flody)