在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径
- 这条路径是两点之间的最短路径
*第一个顶点为源点
*最后一个顶点为终点
问题分类
- 单源 最短路径问题
从固定源点出发，求其到所有其他顶点的最短路径- (有向)无权图
- (有向)有权图
- 多源 最短路径问题
求任意两顶点见得最短路径
有向无权图的单源最短路径
按照 递增 的顺序找出给定节点到各个节点的最短路径
Paste_Image.png
dist[S] = 0
path[]
public UnWeight(Vertex S){
Enqueue(S,Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for( V 的邻接节点 W ){
if(dist[W]!=-1){
dist[W] = dist[V]+1;
path[W] = V;
Enqueue(W,Q);
}
}
}
}
有权有向图的单源最短路径
#dijkstra算法
令 S={源点A+已经确定了最短路径的顶点Vi}
对任一未收录的·顶点v·,定义dist[v] = A 到 v 的最短路径长度。
（但该路径仅仅经过集合S中的顶点）。
若路径是按照 @递增 的顺序生成的=>
{
真正的最短路必须只经过集合S中的顶点。（反证法）
每次从未收录的顶点中选一个dist最小的收录（贪心）。
增加v进入S以后，可能影响另外一个未收录节点w的dist值
#（比如之前不可达，或是之前的到达路径比较长==）
# dist[w]=min(dist[v] + E<v,w>, dist[w])
# E<v，w>表示该边的权重
}
Paste_Image.png
#个人BB
一个富有侵略性的算法。
想象顶点就是一个城池。
占据了顶点以后，依据已经占据的城池向外扩展。
首先扩展就是离出发点最近的领土
（始终是计算出发点和其他点的距离）。
后进来的领土会不会影响旧的领土的距离呢？
@不会
为什么？
加进来的点是按距离顺序添加的。
#代码
void Dijkstra(Vertex s){
while(1){
V = 未收录顶点中dist最小者；
if(没有V){
return;
}
collected[V]=true；
for(V 的每个邻接点 W)
if(collected[W] == false)
if(dist[V] +E(v,w) < dist[W]){
dist[W] = dist[V] + E(v,w);
path[W] = V;
}
}
}
/*不能解决有负边的情况*/
如果遇到负值圈，就可能会陷入一直死循环的情况。
负值圈
- 方法1：直接扫描所有未收录顶点 - O(|V|) 适用于稠密图
- T =O(|V|*|V| + E)
每个节点都要扫一遍。V个点*V
但是其实真是情况是不是，但后面扫的范围会变小呢...因为大部分被加入到了集合collected 中了。
E 是因为要对每个新加入的点的邻接点进行处理，所以每条边都会处理一遍
- 方法2：将dist存在最小堆中-O（log(V)） 适用于稀疏图
- 更新dist[w]的值 - O(log|V|)
- T = O(|N|log|V| + |E|log|V|) = O(|E|log|V|)
多源最短路径问题
#floy算法:
#个人BB
其实和dijkstra有点像。就是不断地添加点到一个集合中。
添加进来的点，
#已经收录的集合到这个点的路径
以及 #这个点到达其他点的路径
暴露了出来。
此时，到达k的路径，以及从k 到达别人的路径保持不变。
改变的是其他要经过k来走最短路径的路。
假设之后，某个点w到k的距离发生了变化，必然是因为加了新的点k1，
那么k1，自然会将 w到k的距离发生变化，而且，会把w经过 k1到达的所有点的距离都会进行改变。
（因为之前，我在担心，k对整个距离产生变化以后，其他点的结果相当于依赖于看k的距离，但是，如果k的距离改变了，那么岂不是其他结果不准了？
其实k距离发生变化，只有可能是有k1加入导致，如果k1导致k发生变化，那么经过k的路径，自然一定要经过k1,
因此k1自然会将所有的后面所能到达的点全部化为更新后的最短路径。
需要多想想。）
public void floyd(){
for(i =0;i<N ;i++){
D[i][j] = G[i][j];
path[i][j] = -1;
}
for(int k=0;k<N;k++){
for(int i =0;i<N;i++){
for(int j=0;j<N;j++){
if(d[i][k]+d[k][j] < d[i][j]){
d[i][j] = d[i][k]+d[k][j];
path[i][j] = k;
}
}
}
}
}
T=O(|V||V||V|)
网友评论