dijkstra算法及其优化
题目描述：给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500 1≤m≤10^5 图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4输出样例：
3
分析：鉴于n的数据规模比较小，可用朴素迪杰斯特拉算法(适用于稠密图)
算法时间复杂度O(n^2)
code：朴素dijkstra算法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int Dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
//迭代n次，每次找到一个点，用它来更新它的可达点到起点的距离。
for(int i=0;i<n;i++){
int t = -1;
//总是选出当前最短路还没有确定的点中到起点最近的点，并用它来更新它的可达点到起点的距离。（这是迪杰斯特拉算法的核心思想--贪心）
//下面是找到当前没有确定最短路的点里到起点距离最短的点。
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t = j;
}
st[t] = true;
//更新可达点
for(int j=1;j<=n;j++) dist[j] = min(dist[j],dist[t] + g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
g[x][y] = min(g[x][y],z);
}
int t = Dijkstra();
printf("%d\n",t);
return 0;
}
分析：同一题，如果n的数据规模增大至10^5
那么，对于这种稀疏图，可以采用堆优化策略的dijkstra算法来求解
代码如下：
//堆优化版dijkstra算法。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
typedef pair<int,int> PII;//第一分量存的是距离，第二分量存的是点编号
int h[N],e[N],ne[N],w[N],idx;//w为边的权值 ，用邻接表来存储稀疏图 ，数据结构类似哈希map，
//h存放的是图中所有结点(h中每个元素将会拉着'一条链',表示该点可达点)，
//e[i] 表示的是第i条边指向的结点，
//ne[i] 表示的是第i条边的下一条边
//w[i] 表示的是第i跳变的权重，
//idx为当前边的编号。
int dist[N];//dist[i] 表示第i个点到起点的距离
bool st[N];//判断第i个点到起点的距离的最短路是否已确定
int n,m;
void add(int a,int b,int c){
e[idx] = b;//idx边所指点是b
w[idx] = c;//idx边的权值是c
ne[idx] = h[a];//下面两行表示将b插入到a的可达点链的最前面。
h[a] = idx++;
}
int Dijkstra(){
//思想与宽搜类似
memset(dist,0x3f,sizeof dist);
//鉴于题意要求最短路，所以采用小根堆来维护每个点到起点的距离，这样堆顶总是最短的路径
//因为dijkstra算法是基于贪心的，所以总用堆顶结点(当前所有点中到起点距离最小的点)来更新堆顶可达点到起点的最短路。
priority_queue<PII,vector<PII>,greater<PII> > p;
dist[1] = 0;
p.push({0,1});//把起点信息入堆，起点到自己距离为0，所以插入的是{0,1};
while(p.size()){
//堆顶出堆
auto t = p.top();
p.pop();
//堆顶可扩展点入堆
int distance = t.first;
int ver = t.second;
//如果ver这个点已近确定了它到起点的最短路，那么可以continue，因为如果它已经确定，那么它的可达点到起点的最短路已经会被它更新，
//所以，重复操作可以得以避免。
if(st[ver]) continue;
for(int i=h[ver];i!=-1;i=ne[i]){
int j = e[i];
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
//可扩展点入堆
p.push({dist[j] , j});
}
}
//ver及其拓展点的最短路信息被更新后就设置ver点的最短路已经确定。
st[ver] = true;
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int t = Dijkstra();
cout<<t<<endl;
return 0;
}