【最短路径】算法7-15：迪杰斯特拉最短路径算法

快来打我* 2022-11-27 15:52 196阅读 0赞

题目描述

在带权有向图G中，给定一个源点v，求从v到G中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。
    在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。
    
    在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。

输入

输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。其中n不超过50，s小于n。
    以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

输出

只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。
    请注意行尾输出换行。

输入

4 1
    0 3 0 1
    0 0 4 0
    2 0 0 0
    0 0 1 0

样例输出

6 4 7

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std; 
    
    const int maxv = 55;
    const int INF = 1000000000;
    
    int n, st, G[maxv][maxv]; //n边数，st起点，G邻接矩阵 
    int d[maxv]; //从起点到各点路径长度 
    bool final[maxv] = {
        false}; //记录是否以及求得起点到各点最短路径 
    
    void DIJ(int s){
        
     fill(d, d + maxv, INF);
     d[s] = 0;
     for(int i = 1; i < n; i++){
         //进行n-1轮操作 
      int u = -1, MIN = INF;
      for(int j = 0; j < n; j++){
         //找出离当前点最近的点 
       if(final[j] == false && d[j] < MIN){
         
        MIN = d[j];
        u = j;
       }
      }
      if(u == -1) return;
      final[u] = true;
      for(int v = 0; v < n; v++){
         //更新当前最短路径长度 
       if(!final[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]){
        
        d[v] = d[u] + G[u][v];
       }
      }
     }
    }
    
    int main(int argc, char** argv) {
        
     scanf("%d%d", &n, &st);
     fill(G[0], G[0] + maxv * maxv, INF);
     for(int i = 0; i < n; i++){
        
      for(int j = 0; j < n; j++){
        
       int wt;
       scanf("%d", &wt);
       if(wt != 0){
        
        G[i][j] = wt;
       }
      }
     }
     DIJ(st);
     for(int i = 0; i < n; i++){
        
      if(i != st){
        
       if(d[i] == INF){
        
        printf("-1 ");
       }else{
        
        printf("%d ", d[i]);
       }
      }
     } 
     printf("\n");
     return 0;
    }