Dijkstra算法正确性证明 精简考试答题版
1. 前置条件与定义
- 适用场景：非负权边的单源最短路径图，源点为s
- 集合定义：S为已确定最短路径的节点集合，U为未确定节点集合
- 变量定义：dist[u]为源点经S内节点到u的当前最短距离，short[u]为源点到u的全局真实最短路径，满足short[u] ≤ dist[u]
2. 核心证明步骤（得分点）
3. 最终结论
由数学归纳法，每一步加入S的节点都获得全局最短路径，算法终止时所有节点的最短路径均被正确求出，算法正确性得证。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<bitset>
#define _for(i,a,b) for (int i=(a);i<(b);i++)
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+5,INF=0x3f3f3f3f;
int n,m;
int e[N],w[N],idx,h[N],ne[N];
int d[N];
bitset<N> vis;
inline void init(){
memset(h,-1,sizeof(h));
idx=0;
}
inline void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dijsktra(){
memset(d,0x3f,sizeof(d));
priority_queue<PII,vector<PII>,greater<PII> > pq;
pq.push({0,1});
d[1]=0;
while (!pq.empty()){
PII now=pq.top();
pq.pop();
if (vis[now.second]){
continue;
}
vis[now.second]=true;
for (int i=h[now.second];~i;i=ne[i]){
int j=e[i];
if (d[j]>now.first+w[i]){
d[j]=now.first+w[i];
pq.push({d[j],j});
}
}
}
return d[n]==INF ? -1 : d[n];
}
int main(){
init();
scanf("%d%d",&n,&m);
_for(i,0,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
printf("%d\\n",dijsktra());
return 0;
}
