# Dijkstra算法模版

Dijkstra算法配合不同的存图方式时间复杂度从`O(N²) ~ O(NE)`，加上优先级队列（堆）的优化能降到`O((m+n)logn)`，那么这篇我列举出一些模版代码，仅供参考。但是我还是更喜欢用SPFA…

Dijkstra & 邻接矩阵存图模版：

``````#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
#define N 105
int map[N][N],vis[N],dis[N];
int n,e,m,s,w;
void dijkstra(){
memset(dis,127,sizeof(dis));
dis[s]=0;
for(int i=1;i<n;i++){
m=21000000;
for(int j=1;j<=n;j++)
if(dis[j]<m && vis[j]==0)
m=dis[j],w=j;    //筛选最短出边，这里可以用priority_queue优化
vis[w]=1;
for(int j=1;j<=n;j++)
if(map[w][j]!=0 && vis[j]==0 && dis[j]>dis[w]+map[w][j])
dis[j]=dis[w]+map[w][j];
}
}
int main(){
cin>>n>>e>>s;
for(int i=1;i<=e;i++){
int x,y,z;
cin>>x>>y>>z;
}
dijkstra();
for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
return 0;
}
/*

5 7 1
1 2 4
1 3 29
3 2 6
2 5 3
3 5 4
4 5 6
1 4 4
*/
``````

``````#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
#define maxn 1002
struct Node{
int e;
int w;
friend bool operator < (Node A, Node B){return  A.w > B.w;}
};
bool vis[maxn];
int m, n;
vector< vector<Node> > G;
int Dij(int Star,int End){
Node P, Pn;
P.e = Star;
P.w = 0;
priority_queue<Node> Q;
Q.push(P);
while(!Q.empty()){
P = Q.top();
Q.pop();
if( vis[P.e] ) continue;
vis[P.e] = true;
if( P.e == End ) return P.w;
int len = G[P.e].size();
for(int i=0; i< len; i++){
Pn.e = G[P.e][i].e;
Pn.w = G[P.e][i].w + P.w;

if( !vis[Pn.e] )
Q.push(Pn);
}
}
return -1;
}
int main(){
Node P;
while(cin >> n >> m, m+n){
G.clear();
G.resize(n+1);
memset(vis,false,sizeof(vis));
for(int i=0; i<m; i++){
int a, b, c;
cin >> a >> b >> c;
P.e = b;
P.w = c;
G[a].push_back(P);
P.e = a;
G[b].push_back(P);
}
int ans = Dij(1,n);
cout << ans << endl;
}
return 0;
}
``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.