①多源最短路

弗洛伊德算法（Floyd）

弗洛伊德算法基本思想就是：

(1) 最开始只允许经过1号顶点进行中转；

(2) 接下来只允许经过1和2号顶点进行中转，以此类推；

(3) 直到最后允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。

算法基本思路：在只经过前k号点的前提下，更新从i号顶点到j号顶点的最短路程。

#include
      
       using namespace std;const int INF=0x3f3f3f3f;const int M=1e3+5;int n,m,e[M][M];void init(){    for(int i=1;i<=n;i++)          for(int j=1;j<=n;j++)              if(i==j)                 e[i][j]=0;                else                 e[i][j]=INF;                      int u,v,w;      for(int i=1;i<=m;i++)      {          scanf("%d%d%d",&u,&v,&w);          e[u][v]=w;      }}void floyd(){    init();    for(int k=1;k<=n;k++)          for(int i=1;i<=n;i++)              for(int j=1;j<=n;j++)                  if(e[i][j]>e[i][k]+e[k][j])                       e[i][j]=e[i][k]+e[k][j];}int main(){      cin>>n>>m;    floyd();    return 0;  }
      

 

---

②单源最短路

迪杰斯特拉算法（Dijkstra）

(1) 最基础的版本，时间复杂度O(2n²)

dist数组：初始点到其余各个顶点的最短路径；

vis数组：下标和dist数组对应；

<1>若值为false，则该点为未确定点，dist数组里的对应值是未确定的；

<2>若值为true，则该点为已确定点，dis数组里的对应值是确定的；

算法基本思路：每次找到离源点（我们目前指定的初始点就是1号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，

不断更新源点到其余所有点的最短路径。

#include
      
       using namespace std;const int INF=0x3f3f3f3f;const int maxSize=1e3+5;int n,m,e[maxSize][maxSize],dist[maxSize];void dijkstra(int x){    int vis[maxSize],i,j,u,minn;    for(i=1;i<=n;i++)    {        dist[i]=e[x][i];        vis[i]=0;    }     vis[x]=1;    for(i=1;i
       
        dist[u]+e[u][j])                dist[j]=dist[u]+e[u][j];            }}int main(){    int i,j,u,v,w,x;    while(cin>>n>>m)    {        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)                if(i==j)e[i][j]=0;                  else e[i][j]=INF;        for(i=1;i<=m;i++)           {            scanf("%d%d%d",&u,&v,&w);            e[u][v]=w;        }        cin>>x;        dijkstra(x);        for(i=1;i<=n;i++)            cout<
        
         <<" ";    }    return 0;}
        
       
      

(2) 链式前向星版本，时间复杂度O(n²）

dis数组：初始点s到其余各个顶点的最短路径；

算法基本思路：从初始点开始作为中介点u，不断加入以中介点u为起点的已存在边的终点v，如果dis[u]+这条边的权值w<dis[v]，则更新dis[v]。

#include
      
       using namespace std;#define MAX 105 #define INF 0x3f3f3f3fint head[MAX],dis[MAX],cn;struct edge{    int w,to,next;}e[MAX*MAX];void add(int u,int v,int w){    e[++cn].w=w;    e[cn].next=head[u];    e[cn].to=v;    head[u]=cn; } void dij(int s){    int he=0,ta=0,qu[MAX*MAX],i;    qu[ta++]=s;    dis[s]=0;    while(he
       
        dis[u]+x.w)            {                dis[x.to]=dis[u]+x.w;                qu[ta++]=x.to;            }        }    }} int main(){    int n,m,i;    while(scanf("%d%d",&n,&m)!=EOF)    {        memset(dis,INF,sizeof(dis));        memset(head,-1,sizeof(head));        for(i=1;i<=m;i++)        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            add(u,v,w);        }        int s;        cin>>s;        dij(s);        for(i=1;i<=n;i++)        cout<
        
         <<" ";    }}
        
       
      

(3) vector邻接表版本，时间复杂度O(n²)

算法基本思路：与链式前向星版本同理。

#include
      
       using namespace std;#define MAX 10005#define INF 0x3f3f3f3ftypedef pair
       
         pii;vector
        
         vec[MAX];int dis[MAX];void dij(int s){    memset(dis,INF,sizeof(dis));    dis[s]=0;    int qu[MAX],he=0,ta=0,i;    qu[ta++]=s;    while(he
         
          dis[u]+w)            {                dis[v]=dis[u]+w;                qu[ta++]=v;            }        }    }}int main(){    int n,m,i;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1;i<=m;i++)        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            vec[u].push_back(pii(v,w));        }        int s;        cin>>s;        dij(s);        for(i=1;i<=n;i++)        cout<
          
           <<" ";    }    return 0;}