写在前面：
前面我们说到Dijkstra算法，每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，可以用优先队列（堆）来优化，使得这一部分的时间复杂度降低到。
代码实现：
【vector+优先队列 优化Dijkstra】
#include<iostream>
#include<cstdio>
#include<vector>// vector
#include<queue>// priority_queue
using namespace std;
const int Maxsize=1e4+5;// 顶点数量的最大值
const int INF=0x3f3f3f3f;// 正无穷大
// 边的结构体
struct edge
{
int d,v;// d:距离；v：节点(弧头)
edge(){}
edge(int a,int b)// 初始化 d 和 v
{
d=a,v=b;
}
// 重载"<"运算符，以便更改优先队列的排序规则
// 根据"最短距离"d来进行排序
bool operator < (const edge&x)const
{
if(d==x.d)return v<x.v;
else return d>x.d;
}
};
vector<edge>G[Maxsize];// 图 G
int dis[Maxsize];// 距离表
int n,m;// n:顶点个数 m:边数
int v1,v2,w;// v1->v2,weight==w
// Dijkstra算法，源点为 s
void dijkstra(int s)
{
// 初始化dis数组
for(int i=0;i<=n;i++)dis[i]=INF;
dis[s]=0;
priority_queue<edge>que;// 优先队列
que.push(edge(dis[s],s));// 将起点压入队列
// 队列非空
while(!que.empty())
{
// get the min_index
edge temp=que.top();
que.pop();
int v=temp.v;// 顶点
if(dis[v]<temp.d)continue;//
// 遍历顶点v相连的所有边
for(int i=0;i<G[v].size();i++)
{
edge e=G[v][i];
if(dis[e.v]>dis[v]+e.d)
{
dis[e.v]=dis[v]+e.d;
que.push(edge(dis[e.v],e.v));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
G[i].clear();
}
while(m--)
{
scanf("%d%d%d",&v1,&v2,&w);
G[v1].push_back(edge(w,v2));
G[v2].push_back(edge(w,v1));
}
dijkstra(1);
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
puts("");
}
【vector实现邻接表+优先队列 (假设边一开始是字符型的，这么假设是为了加点难度)】
因为顶点是字符型，所以需要用到映射map来解决。
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=205;
const int INF=0x3f3f3f3f;
typedef pair<int,int>pii;// 相当于struct pii
int n,m;// 点，边
int dis[N];// 距离表
string src,ed;// src:起点；ed:终点
// 用结构体存放边和权值
struct edge
{
int u;// 起点(弧尾)
int v;// 终点(弧头)
int w;// 边权
edge(){}// 构造函数
edge(int uu,int vv,int ww):u(uu),v(vv),w(ww){}
};
map<string,int> M;// 给的点是字符串，map转换成数字
vector<edge>G[N];// 图 G
void init()
{
M.clear();// 对于每个case，每次循环对M清空
int cnt=0;// 为了给每个字符串key，一个value，value值就是cnt++
cin>>n>>m;// 输入点数和边数
string u,v;// 输入字符型的节点，用于一会输入
int w;// 每条边的权值
// 输入每条边的信息
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;// 输入边和权值
// 如果M（map定义的）里面没有这个key，就将他插入将他对应为++cnt值，
// 如果有，不变，意味着，cnt不变，这时的u仍为原来的value值
if(!M.count(u))
{
// 用make_pair()函数，将key和value（给每个的编号）值插入M（map）
M.insert(make_pair(u,++cnt));
}
//同理,这些都是为了将字符串用数字编号表示
if(!M.count(v))
{
M.insert(make_pair(v,++cnt));
}
// 用struct构造两个方向的边，且用构造函数赋值，两点的编号，和边的权值
// 从而合成，无向的图-->这样得到两条边的信息
edge E1(M[u],M[v],w);
edge E2(M[v],M[u],w);
G[M[u]].push_back(E1);// 建立邻接表，用vector表示，将这一条边E1压入邻接表
G[M[v]].push_back(E2);// 另一条边也压入邻接表
}
cin>>src>>ed;// 输入最终要求的，起点和终点，编号就是M[src],M[ed]
// 初始化dis，dis里存的是，起点src到各点的最短距离，dis[src]为零，其他的初始化为inf
for(int i=1;i<=m;i++)
{
dis[i]=(i==M[src]?0:INF);
}
}
void Dijkstra()
{
// 优先队列，用pair，相当于一个新的结构体，有两个属性
priority_queue<pii,vector<pii>,greater<pii> > que;
// 用make_pair()将起点压入优先队列(即通过pair的两个属性)。距离和编号
que.push(make_pair(0,M[src]));
// 优先队列不为空
while(!que.empty())
{
// 声明一个新的pii tmp。让tmp存放优先队列队前的元素，因为是greater，即que.top就是目前队列里最短距离
pii tmp=que.top();
// tmp拥有了优先队列里最小值的两个属性分别赋给了tmp.first（距离）和tmp.second（编号）
que.pop();// 把这个点清掉（开始时，清理的是起点）
int x=tmp.second;// x存放编号
if(tmp.first!=dis[x])// 如果距离和他带的点的距离不一样了，说明这个点处理过了，continue跳过这个点
continue;
for(int i=0;i<G[x].size();i++)
{
int y=G[x][i].v;// y存放邻接表的的v值
int w=G[x][i].w;
if(dis[y]>dis[x]+w)// 如果距离
{
dis[y]=dis[x]+w;
que.push(make_pair(dis[y],y));// 压入队列
}
}
}
}
int main()
{
int ttt;
cin>>ttt;
while(ttt--)
{
init();// 初始化，和输入
Dijkstra();// dijkstra函数
if(dis[M[ed]]==INF) cout<<"-1"<<endl;// 如果不联通，输出-1
else cout<<dis[M[ed]]<<endl;//可 以写成，cout<<(dis[M[ed]]==INF?-1:dis[M[ed]]])<<endl;
}
return 0;
}
【数组实现邻接表+优先队列】
直接放了代码，因为时间关系，就没有自己码一边，有错还望指出。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int MAXN = 205;
int dis[MAXN];
int u[MAXN],v[MAXN],w[MAXN];
int first[MAXN],next[MAXN];
int n,m;
int src,ed;
typedef pair<int,int> pii;
void init()
{
scanf("%d%d",&n,&m);
memset(first,-1,sizeof(first));
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
next[i]=first[u[i]];
first[u[i] ]=i;
u[i+m]=v[i],v[i+m]=u[i],w[i+m]=w[i]; //无向边，所以加一条反向边
next[i+m]=first[u[i+m] ];
first[u[i+m] ]=i+m;
}
cin>>src>>ed;
for(int i=1;i<=n;i++) dis[i]= (i==src? 0:inf);//不要把dis[i]初始化成源点到各点的直接距离，否则会有点没入队。
}
void dijkstra()
{
priority_queue<pii,vector<pii>,greater<pii> >que;
que.push(pii(0,src));
while(!que.empty()){
pii tmp=que.top();
que.pop();
int x = tmp.second;
if(tmp.first!=dis[x]) continue; //如果出队的这个元素,他带的dis,和当前的dis不相同，证明这个结点是被处理过的已确定了最短路，
for(int e=first[x];e!=-1;e=next[e]){ //这种数组式邻接表的遍历
if(dis[v[e]]>dis[x]+w[e]){
dis[v[e] ]=dis[x]+w[e];
que.push(pii(dis[v[e] ],v[e]));
}
}
}
}
int main()
{
// freopen("1.in","r",stdin);
int _;
scanf("%d",&_);
while(_--){
init();
dijkstra();
if(dis[ed]==inf) cout<<"-1"<<endl;
else cout<<dis[ed]<<endl;
for(int i=1;i<=n;i++) printf("%d ",dis[i]);//输出dist数组各个值
putchar('\n');
}
}
写在最后：
参考资料：
- 博客：再谈Dijkstra算法和堆优化
- 博客：Dijkstra + 优先队列 + 邻接表优化
- 博客：Dijkstra[两种邻接表+优先队列优化]（代码参考）
- 博客：C++中priority_queue的简单用法（优先队列）
- 博客：priority_queue的用法（优先队列）
优先队列，在最近的学习中，用的频率挺多的，后面有时间再来仔细研究其实现原理。
图论是真的难呀，建图可以建一年……慢慢来吧！！！
网友评论