单源最短路径
一、最短路径概念：
1、最短路路径树
在最短路径算法结束时，Gπ为最短路径树Gπ=(Vπ,Eπ)
Vπ={v∈V: π[v]≠NIL}∪{s}
Eπ={(π[v],v)∈E: v∈Vπ-{s}}
最短路径不一定唯一，∴最短路路径树也不一定唯一
2、松弛技术——逼近及最终达到最短路径
(基础)
引理25.1：最短路径的子路径也是最短路径
(不等式:逼近最短路径)
引理25.3：所有有向边都“有权利”(be entitled to)做最短路径的最后一条边
??? 设G=(V,E)是一个有向加权图，其加权函数为w:E→R，源节点为s。
??? 则对所有边(u,v)∈E，有
??? dis(s,v)≤dis(s,u)+w(u,v)，其中dis(i,j)为结点i到j的最短路径(d[v]是s~~>v最短路径的估计)
???
initialize-single-source(G,s)
??? for 每个顶点v∈V[G]
??? ??? do??? d[v] <- ∞
??? ??? ??? pi[v] <- NIL
??? ??? d[s] <- 0
relax(u,v,w)
??? if??? d[v] > d[u]+w(u,v)
??? ??? then??? d[v] <- d[u]+w(u,v)
??? ??? ??? ??? pi[v] <- u
??? ??? ??? ???
每一步松弛实际上就是“引理25.3”的实践!
(等式:达到最短路径)
引理25.7：设G=(V,E)是一个有向加权图，其加权函数为w:E→R，源节点为s。
??? ??? ? 且对于某些结点u,v∈V，设s~~>u->v是G的一条最短路径。
??? ??? ?假定过程initialize-single-source(G,s)已对G进行了初始化，且
??? ??? ?随即对G的边执行了包含调用RELAX(u,v,w)的一个松弛操作序列。
??? ??? ?如果在调用前的任何时刻d[u]=dis(s,u)，则调用以后d[v]=dis(s,v)
??? ??? ?始终保持成立。
下面两个图帮助记忆引理25.7，灰常重要——
?
A. 万事俱备，只欠东风
????????????????? -------------------------------------------------------------------->time
???? (1)initialize-single-source(G,s)???? (2)d[u]=dis(s,u)???? (3)东风：relax(u,v,w)???? (4)d[v]=dis(s,v)
?
B.??? s? ~~~~~~~~~~~>? u ?? -> ?? v
???? d[u]已更新到dis(s,u) ???? 若s~~>u->v是某条最短路径，只需relax(u,v,w)一下，就可最终更新d[v]到dis(s,v)
?
????? 总结：前面两个引理分别是“所有推导的基础（引理25.1）”和“逼近最短路径（25.3）”，但没有真正到达最短路径。通过引理25.7，我们真正达到了最短路径。据此，可以设计出各种算法，来实现引理25.7的前提；此时，dis[]中自然就是我们需要的单源最短路径鸟:)
?
3. 最短路的4种重要算法
??? （1）Dijkstra
?????????????? Haha，我能感觉到(I CAN REALLY FEEL) Dijkstra算法在被设计时，目标就是达到“引理25.7”的前提，这样，当算法执行完了所有顶点v的d[v]就自动减小到dis[s,v]了！Can you feel it?吼吼吼吼
??? （2）Bellman-Ford
?????????????? 另外，BellmanFord算法也和Dijkstra一样，也来自“引理25.7”，因为在算法运行的过程中完成了“所有顶点的所有排列方式”对应的边的松弛操作。例如，假设有顶点1,2,3，则这个算法考虑到了一下三种顺序的松弛:
?????????????? 松弛边<1,2>, 松弛边<2,3>;
?????????????? 松弛边<1,3>, 松弛边<3,2>;
?????????????? 松弛边<2,1>, 松弛边<1,3>;
?????????????? 松弛边<2,3>, 松弛边<3,1>;
?????????????? 松弛边<3,1>, 松弛边<1,2>;
?????????????? 松弛边<3,2>, 松弛边<2,1>.
??? （3）DAG的单源点最短路径
void Spfa(){ d[S]=0; v[S]=true; deque <int> q; for(q.push_back(S);!q.empty();) { int x=q.front(); q.pop_front(); for(int k=head[x];k!=-1;k=el[k].next) { //每次处理一条邻接边<x,i>: el[k] //el[k].y 指向的顶点 //el[k].c 有向边el[k]的代价 //el[k].next 从x出发的下一条邻接边 int y=el[k].y; if(d[y]>d[x]+el[k].c) { d[y]=d[x]+el[k].c; //仅当顶点y不在队列中时，才入队；否则即使松弛了，也不作任何处理 if(!v[y]) { v[y]=true; //顶点第一次y被访问到v[y]=true //保持队列中所有元素i按照d[i]递增排列 if(!q.empty()) { if(d[y]>d[q.front()]) q.push_back(y); else q.push_front(y); } else q.push_back(y); } } } v[x]=false; } return ;}?
*********************************************************************
二、性能及其他
1、BellmanFord和Dijkstra执行之前都需要相同的初始化
2、BellmanFord注意：
??? 1)有向图中没有边的顶点设置为Integer.MAX_VALUE/2
??? （若设置为Integer.MAX_VALUE可能导致越界错误，而且这个错误时RE）
??? 2)有向图中，i=j时，m[i][j]=0
3、关于速度：
??? BellmanFord: O(VE)? --当用权值矩阵表示图时(通常是这么做的)-->O(V^3)
??? Dijkstra:??? O(V^2) ——普通数组实现优先队列
??? ??? ??? ??? ?O((V+E)lgV)??? ——最小二叉堆实现优先队列
??? ??? ??? ??? ?O(VlgV+E)??? ??? ——斐波那契堆实现优先队列
???
4、我认为，一般情况下，Dijkstra比BellmanFord要快一些；但Dijkstra要求边权非负，而BellmanFord只要求
单源点不能到达负权回路即可（这是最短路径问题都需要保证的，否则最短路可能为-∞）。看来老天是公平的，不
会让你什么都占优势!
?
5、“单汇点的最短距离”问题可以转换为: 对转置图的“单源点最短路径”! 千万别去计算每对顶点的最短距离TT