其实这两个，都用了三角形不等式，就是如果通过中介节点可以比原来的还小，那就更新
（单源最短路）
有个区别就是，dijkstra 是通过优先队列，这样每次都取最小的，每次都取最小的话，最小的不会被其他节点更新，所以只需要一次
也就是说，只要它出过队列，他就可以不用在出一次了，所以我们的标记数组放在出队列的地方，一旦标记过就没有必要再找了
只不过，dijkstra不能负权值
spfa可以负权值
但是它的标记是进queue标记，出queue撤销标记，，，所以每个节点可以标记无数次，，，，所以在有些情况下，这玩意很慢的
注意：
注意Next的应用
注意priority_queue是默认大根堆，，，，，，，，所以存的时候就弄相反数就可以变成小根堆啦
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 6 using namespace std; 7 const int N=10010,M=1000010; 8 int head[N],ver[N],edge[M],Next[M],d[N],v[N]; 9 int n,m,tot=0; 10 void add(int x,int y,int z){//i->j,edge=z 11 ver[++tot]=y; 12 edge[tot]=z; 13 Next[tot]=head[x]; 14 head[x]=tot;//tot是当前的个数，从１开始 15 } 16 priority_queue<pair<int,int> > q; 17 /* 18 Next是该x所对应的下一个数 19 */ 20 void dijkstra(){ 21 memset(d,0x3f,sizeof(d)); 22 memset(v,0,sizeof(v)); 23 d[1]=0; 24 q.push(make_pair(0,1)); 25 while(q.size()){ 26 int x=q.top().second; 27 q.pop(); 28 if(v[x]) continue; 29 v[x]=1; 30 for (int i = head[x]; i ; i=Next[i]) {//Next相当于把x存起来了 31 int y=ver[i],z=edge[i]; 32 if(d[y]>d[x]+z){ 33 d[y]=d[x]+z; 34 q.push(make_pair(-d[y],y));//相反数变小根堆 35 } 36 37 38 } 39 } 40 41 42 } 43 int main(){ 44 cin>>n>>m;//n是点集,m是n边集 45 for (int i = 1; i <= m; i++) 46 { 47 int x,y,z; 48 cin>>x>>y>>z; 49 add(x,y,z); 50 } 51 dijkstra(); 52 for (int i = 1; i <= n; i++) 53 { 54 /* code */ 55 cout<<d[i]<<endl; 56 } 57 58 59 60 }
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<string> 8 #include<vector> 9 #include<queue> 10 #include<map> 11 #include<set> 12 #include <unordered_set> 13 using namespace std; 14 const int N=10010,M=1000010; 15 int head[N],ver[N],edge[M],Next[M],d[N],v[N]; 16 int n,m,tot=0; 17 void add(int x,int y,int z){//i->j,edge=z 18 ver[++tot]=y; 19 edge[tot]=z; 20 Next[tot]=head[x]; 21 head[x]=tot;//tot是当前的个数，从１开始 22 } 23 queue<int> q; 24 void spfa(){ 25 memset(d,0x3f,sizeof(d)); 26 memset(v,0,sizeof(v)); 27 d[1]=0; 28 v[1]=1; 29 q.push(1); 30 while(!q.empty()){ 31 int x=q.front(); 32 q.pop(); 33 v[x]=0; 34 for (int i=head[x];i;i=Next[i]) { 35 int y=ver[i]; 36 int z=edge[i]; 37 38 if(d[y]>d[x]+z){ 39 d[y]=d[x]+z; 40 if(!v[y]){ 41 q.push(y); 42 v[y]=1; 43 } 44 } 45 46 } 47 } 48 49 50 } 51 52 int main(){ 53 cin>>n>>m;//n是点集,m是n边集 54 for (int i = 1; i <= m; i++) 55 { 56 int x,y,z; 57 cin>>x>>y>>z; 58 add(x,y,z); 59 } 60 spfa(); 61 for (int i = 1; i <= n; i++) 62 { 63 /* code */ 64 cout<<d[i]<<endl; 65 } 66 67 68 69 }
加一个多源最短路的链接https://www.cnblogs.com/zhmlzhml/p/12950663.html