- Dijkstra英文wiki：传送门，中文博客：传送门
- Dijkstra+优先队列：传送门
- 本篇所有知识点部分（及其拓展链接）均采用C++进行介绍。
- Tag：图论
前置知识
- 优先队列：时间复杂度O（lg（n））
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。（其实就是大/小顶堆的实现，一般来说寻路都是寻最短路，所以每次应去除最小值，所以一般情况下构建的都为小顶堆）
//二叉小顶堆-优先队列
#include <iostream>
#define Max_N 1010
using namespace std;
int Heap_size;
int Heap[Max_N];
//插入操作
void push(int x)
{
int indx=++Heap_size;//首先插入到最后一个位置
//向上调整
while(indx>1)//只有i>1才会有父节点
{
int parent_indx=indx/2;//父节点编号
if(Heap[parent_indx]<=x)//没有上下颠倒就结束调整
break;
Heap[indx]=Heap[parent_indx];//大小颠倒就将当前节点上调
indx=parent_indx;
}
Heap[indx]=x;
}
//删除操作
int pop()
{
int result=Heap[0];//获取最值
int x=Heap[--Heap_size];//相当于将最后的一个元素放到根节点
int index=1;
while(2*index<=Heap_size)//一定要有子节点
{
int L_son_index=2*index;
int R_son_index=2*index+1;
//比较儿子节点的最值
int Min_index=L_son_index;
if(R_son_index<=Heap_size && Heap[R_son_index]<Heap[Min_index])
Min_index=R_son_index;
//如果没有上下颠倒就结束
if(Heap[Min_index]>=x)
break;
//上下颠倒就交换
Heap[index]=Heap[Min_index];
index=Min_index;
}
Heap[index]=x;
return result;
}
void Build_Heap(int data[],int n)
{
//创建一个空堆
Heap_size=0;
for(int i=0;i<n;i++)//逐个插入元素
push(data[i]);
}
int main()
{
int n;
int data[Max_N];
cin>>n;
for(int i=0;i<n;i++)
cin>>data[i];
for(int i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<endl;
Build_Heap(data,n);
for(int i=1;i<=Heap_size;i++)
cout<<Heap[i]<<" ";
cout<<endl;
return 0;
}
Dijkstra+Priority_Queue模板
#include<stdio.h>
#include<algorithm>
#include<queue>
#define INF 2147483647
using namespace std;
typedef pair<int,int> pii;
int u[150000],v[150000],w[150000],next[150000],first[150000],n,m,d[150000], tot;
int maxn[21];
bool done[150000];
priority_queue<pii,vector<pii>,greater<pii> >q;
void addedge(int st, int end, int val)
{
u[++tot] = st;
v[tot] = end;
w[tot] = val;
next[tot] = first[st];
first[st] = tot;
}
void dij(int a)
{
int i;
for(i = 1; i <= n; i++)d[i] = INF;
d[a] = 0;
q.push(make_pair(d[a],a));
while(!q.empty())
{
int x = q.top().second;q.pop();
if(done[x])continue;
done[x] = true;
for(int e = first[x];e != -1; e = next[e])
if(d[v[e]] > d[x] + w[e])
{
d[v[e]] = d[x] + w[e];
q.push(make_pair(d[v[e]], v[e]));
}
}
}
int main()
{
int i;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++)first[i] = -1;
for(i = 1; i <= m; i++)
{
int st,end,val;
scanf("%d%d%d", &st, &end, &val);
addedge(st, end, val);
addedge(end, st, val);
}
dij(1);
printf("%d ", d[3]);
return 0;
}