Peter算法小课堂—Dijkstra最短路算法

大家好，我们人见人爱、花见花开、车见车爆胎的Peter Pan来啦，hia~hia~hia。今天，我们今天来学习毒瘤的最短路算法啦。啊这……什么是Dijkstra算法？长文警告⚠

正经点啊

手算样例

大家思考一下，你在手算样例的时候，你是怎么计算的，总结一下规律。

 Dijkstra

在大多数最短路算法中（好像只学了一个），Dijkstra算法是最常用、效率最高的一个。他是解决单源多汇问题的，单源多汇问题简称SSSP，即计算一个起点到其他所有点的最短距离长度。

这题是无权图，所以说只是用来练练BFS，过会儿Dis算法要用到BFS。

大家练一练，十分钟后开放代码。

是不是想偷看代码了？

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2009;
vector<int> to[N];
bool vst[N];
int n,m,d[N];
void bfs(){queue<int> q;vst[1]=1;d[1]=0;q.push(1);while(!q.empty()){int u.q.front();q.pop();for(int i=0;i<=to[u].size();++i){int v=to[u][i];if(vst[v]) continue;vst[v]=1;d[v]=d[u]+1;q.push();}}for(int u=1;u<=n;u++){if(!vst[u]) cout<<-1<<" ";else cout<<d[u]<<" ";}
}
int main(){cin>>n>.m;for(int i=1;i<=m;++i){int u,v;cin>>u>>v;to[u].push_pack(v);}bfs();

 来看第二题

BFS

步骤：1.从起点s出发，用BFS扩展它的邻居节点。把这些点放进一个集合A中，并记录这些点到s的距离。2.选择距离s最近的邻居v，继续用BFS扩展v的邻居。3.重复步骤2，直到所有点都扩展到并计算完毕。那么复杂度是多少呢？一般，A用优先队列模拟。一共向队列中插入m次，取出n次，假设每一个点平均有k个邻居，那么总复杂度为 

代码差不多这样

#include <bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int N=3e5+2;
struct edge{int from,to;long long w;edge(int a,int b,long long c){from=a;to=b;w=c;}
};
vector<int> e[N];
struct node{int id;long long n_dis;node(int b,long long c){id=b,n_dis=c;}	
};
int n,m;
int pre[N];
long long dis[N];
bool done[N];
void dijkstra(){int s=1;for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}dis[s]=0;priority_queue<node> Q;Q.push(node(s,dis[s]));while(!Q.empty()){node u=Q.top();Q.pop();if(done[u.id]) continue;done[u.id]=true;for(int i=0;i<e[u.id].size();i++){edge y=e[u.id][i];if(done[y.to]) continue;if(dis[y.to]>y.w+u.n_dis){dis[y.to]=y.w+u.n_dis;Q.push(node(y.to,dis[y.to]));pre[y.to]=u.id;}}}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) e[i].clear;while(m--){int u,v,m;cin>>u>>v>>m;e[u].push_back(edge(u,v,m));}dijkstra();for(int i=1;i<=n;i++){if(dis[i]>=INF) cout<<"-1";else cout<<dis[i];}return 0;
}

请同学们进行上机练习，练习题目即将公布。

POJ2449

“好男人从来不会让女孩子等待或破坏约会！”鸳鸯爸爸说。他轻轻地抚摸着小鸭子的头，给它们讲了一个故事。

“雷马古茨王子住在他的王国UDF——自由联合三角洲。有一天，他们的邻国派他们乌尤公主去执行外交任务。

“埃雷诺，公主给雷马古茨写了一封信，告诉他，当且仅当王子通过K条最短的路径去见她时，她才会来到大厅与UDF进行商业谈判。（事实上，Uyuw根本不想来）“

对贸易发展和这样一个可爱的女孩感兴趣，雷马古茨王子真的被迷住了。他需要你——首相的帮助！

详细信息：UDF的首都由N个站点组成。大厅编号为S，而车站编号为T表示王子的当前位置。M泥泞的侧向连接一些车站。Remmarguts欢迎公主的路径可能包括两次或两次以上的同一车站，即使是编号为S或T的车站。

太戈编程1817

中国象棋中的“马”走“日”字，我们要研究马在棋盘格里的行走规律。已知棋盘格共有10行9列个格点，马的起始位置为第r1行第c1列，目标位置是第r2行第c2列。请求出从起点到目标格点的最少步数，若无法走到就输出-1。注意马不可以走出棋盘格范围。

太戈编程637

n个星球编号为1,2,3,...,n。星球间可能有直飞火箭往返，每条火箭航线的航行时间用邻接矩阵表示，如果两个城市间没有直飞，用-1表示。求1号星球到各星球最少时间？ 若无法到达输出-1。n<=500

太戈编程638

作为武林盟主，你希望邀请各门派高手来武林大会切磋武艺。共有n个门派，分散在江湖上不同位置，编号1到n，大会将在1号门派举办。对于第i个门派，你打算邀请1个人参会。从任意门派i号到任意不同门派j号有单向通路，路费为（i*666+j*j）mod 233。本次武林大会的所有路费由你承担，请问总费用至少多少？

希望这些对大家有用，三连必回