前言

提示：以下是本篇文章正文内容，下面案例可供参考

一、dijkstra一般迪杰克斯拉

#include 
   
    #include 
    
     //头文件（用于INT_MAX）因为int的最大值记不住using namespace std;int a[1005][1005];//邻接矩阵int d[1005];//存放最短路径bool v[1005];//标记是否访问过int n,m,cnt;//n为顶点个数,m为有几条边,minx为最小路径（一般初始化为inf）,cnt为源点（初始点）int main(){
       cin>>n>>m>>cnt;//输入n,m,cnt    for(int i=1;i<=n;i++){
   //初始化邻接表，当i==j时为0，否则为INX_MAX（也就是int类型的最大值）        for(int j=1;j<=n;j++){
               if(i==j)            a[i][j]=0;            else            a[i][j]=INT_MAX;        }    }    for(int i=1;i<=m;i++){
           int x,y,z;//输入邻接表的值        cin>>x>>y>>z;//表示的是x点到y点的权值        a[x][y]=z;//有向图       // a[y][x]=z;//无向图    }    for(int i=1;i<=n;i++){
           d[i]=a[cnt][i];//初始化源点到每个点的权值，若不连通则为INT_MAX    }    v[cnt]=1;//将源点设为以访问    //dijkstra算法核心代码    for(int i=1;i<=n-1;i++) {
           int minx = INT_MAX, k;//最短路径赋初值        for (int j = 1; j <= n; j++) {
   //遍历点            if (!v[j] && d[j] < minx) {
   //如果该点未被访问，得出最短路径                minx = d[k = j];//记录这个点能用最短路径到达下一个点（点的序号）            }        }        v[k] = 1;//将这个点设置为已访问        for (int j = 1; j <= n; j++) {
               if (a[k][j] < INT_MAX) {
   //注意:k点到j点的权值不能大于INT_MAX                if (d[j] > d[k] + a[k][j]) {
   //如果先到达k点再到达j点的路径，比直接到达j点的路径要短                    d[j] = d[k] + a[k][j];//就将这个最短路径记录下来,而不是用本身的d[j]                }            }        }    }    for(int i=1;i<=n;i++){
           cout<
     
      <<" ";//最后输出源点到图里各个点的最短路径    }    return 0;}

二、dijkstra 链式星存图+优先队列+堆优化

代码如下（示例）：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int N=1e5+5;const int M=2e5+5;int head[N],nxt[M],to[M],val[M],cnt;int d[N],v[N],n,m,s;priority_queue
       
        
          > q;void add(int a,int b,int c){ nxt[++cnt]=head[a]; to[cnt]=b; val[cnt]=c; head[a]=cnt;}void dijkstra(){ for(int i=1;i<=n;i++) d[i]=INT_MAX; d[s]=0; q.push(make_pair(0,s)); while(!q.empty()){ int u=q.top().second; q.pop(); if(v[u]) continue; v[u]=1; for(int i=head[u];i;i=nxt[i]){ int v=to[i]; int w=val[i]; if(d[v]>d[u]+w){ d[v]=d[u]+w; q.push(make_pair(-d[v],v)); } } }}int main(){ cin>>n>>m>>s; for (int i = 1; i <=m ; ++i) { int u,v,w; cin>>u>>v>>w; add(u,v,w); } dijkstra(); for (int i = 1; i <=n ; ++i) { if(d[i]==0x3f3f3f3f) cout<<2147483647<<' '; else cout<
         
          <<' '; } return 0;}

三、floyd弗洛伊德

代码如下（示例）：

#include
   
    using namespace std;#define inf 1234567890#define maxn 10005inline int read(){
       int x=0,k=1; char c=getchar();    while(c<'0'||c>'9'){
   if(c=='-')k=-1;c=getchar();}    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();    return x*k;}//快读int a[maxn][maxn],n,m,s;inline void floyd(){
       for(int k=1;k<=n;k++)        //这里要先枚举k（可以理解为中转点）    {
           for(int i=1;i<=n;i++)        {
               if(i==k||a[i][k]==inf)            {
                   continue;            }            for(int j=1;j<=n;j++)            {
                   a[i][j]=min(a[i][j],a[i][k]+a[k][j]);                //松弛操作，即更新每两个点之间的距离                //松弛操作有三角形的三边关系推出                //即两边之和大于第三边            }        }    }}int main(){
       n=read(),m=read(),s=read();    for(int i=1;i<=n;i++)    {
           for(int j=1;j<=n;j++)        {
               a[i][j]=inf;        }    }    //初始化，相当于memset(a,inf,sizeof(a))    for(int i=1,u,v,w;i<=m;i++)    {
           u=read(),v=read(),w=read();        a[u][v]=min(a[u][v],w);        //取min可以对付重边    }    floyd();    a[s][s]=0;    for(int i=1;i<=n;i++)    {
           printf("%d ",a[s][i]);    }    return 0;}

四、floyd

#include "iostream"const int N=1e4+5;const int inf=1234567890;using namespace std;int a[N][N],n,m,s;bool v[N];void floyd(){
       for (int k = 1; k <=n ; ++k) {
           for (int i = 1; i <=n ; ++i) {
               if(i==k||a[i][k]==inf) continue;            for (int j = 1; j <=n ; ++j) {
                   a[i][j]=min(a[i][j],a[i][k]+a[k][j]);            }        }    }}int main(){
       cin>>n>>m>>s;    for (int i = 1; i <=n ; ++i) {
           for (int j = 1; j <=n ; ++j) {
               if(i==j)                a[i][j]=0;            else                a[i][j]=inf;        }    }    for (int i = 1; i <=m ; ++i) {
           int u,v,w;        cin>>u>>v>>w;        a[u][v]=min(a[u][v],w);    }    floyd();    for (int i = 1; i <=n ; ++i) {
           cout<
   
    <<' ';    }    return 0;}

五、bellmon-floyed

#include
   
    #define INF 0x7fffffff#define MAXN 10005#define int long longusing namespace std;int edge[MAXN][MAXN],dis[MAXN];int n,m,s;void BellmanFord(){
       dis[s]=0;    for(int k=1;k<=n;k++){
   //一共要进行 n 轮松弛        for(int i=1;i<=n;i++){
               for(int j=1;j<=n;j++){
                   dis[i]=min(dis[i],dis[j]+edge[j][i]);            }        }    }}signed main(){
       cin>>n>>m>>s;    for(int i=0;i<=n;i++)dis[i]=INF;    for(int i=0;i<=n;i++)        for(int j=0;j<=n;j++)edge[i][j]=INF;    for(int i=0;i
    
     >u>>v>>w;        edge[u][v]=min(edge[u][v],w);    }BellmanFord();    for(int i=1;i<=n;i++)cout<
     
      <<' ';    return 0;}