说实在的，这算法很简单，很简单，很简单……因为它是贪心的，而且码量也小，常数比起SPFA也小。

主要思想

先初始化，dis[起点]=0，其它皆为无限大。

还要有一个bz数组，bz[i]表示i是否确定为最短路径

for i=1 to n {    在未确定最短路径的点中找出u使dis[u]最小    bz[u]=1;    更新与u相连的所有点}

就这么简单。

实现讲解

其实也很好实现。可以用邻接表储存，也可以用邻接矩阵储存，虽然会慢一点。因为Dijkstra算法本就是对付稠密图的，不过我还是建议用邻接表，见

注意事项

Dijkstra不能处理负边权的状况，所以要看清题目大意才用它哦！

具体代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;struct _Way//定义_Way类型，表示某点到点y的距离为len {    int y,len;  };int n,m;int q;_Way way[1001][1001] {};//way[i][j]表示从i开始的第j条路 _Way* bz[1001][1001] {};//读入时标记，防止重边出现。bz[i][j]指向从i到j的直接路径 int now[1001] {};//now[i]表示从i开始的边的数量 int dis[1001] {};//dis[i]表示从起点到i的最短路径 int min(int a,int b){
   return a
         
          >n>>m; for(int i=1;i<=m;i++) { int x,y,len; cin>>x>>y>>len; if (bz[x][y]!=NULL)//若重边则替换之 { bz[x][y]->len=min(bz[x][y]->len,len); continue; } now[x]++; way[x][now[x]].y=y; way[x][now[x]].len=len; bz[x][y]=&(way[x][now[x]]);//标记好地址 } cin>>q; Dijkstra(q); for(int i=1;i<=n;i++) { if (dis[i]!=INT_MAX) cout<
          
           <
          
         
        
       
      
     
    

优化

用堆优化，暂时不会。

SPFA和Dijkstra哪个强？

SPFA擅长于稀疏图，而Dijkstra擅长于稠密图

SPFA可以处理负边权，Dijkstra不可以处理负边权

SPFA时间复杂度为O(kE)，Dijkstra时间复杂度为O(n^2)

SPFA的空间要比Dijkstra多一个队列

SPFA的优化有SLF和LLL，Dijkstra的优化有堆优化

SPFA和Dijkstra均不可以处理负权回路

SPFA的时间系数要比Dijkstra大（Floyed和Ford笑了）

SPFA和Dijkstra都是单源的（Floyed又笑了）

没有边的图 O(1)特殊判断 SPFA秒过，完全图Dijkstra秒过（Floyed和Ford骄傲地说：“我们的时间是固定的！”）