图之习题选讲-旅游规划
图习题.1 核心算法
题意理解
- 城市为结点
- 公路为边
- 权重1：距离
- 权重2：收费
- 单源最短路
- Dijkstra算法 ——距离 (一个结点一个结点往那个集合里面去收集，每收进来一个就要检查以下其他结点距离有没有被新进来的结点影响，得到更短的距离就刷新掉，得不到就保持原样)
- 等距离时按收费更新
核心算法
最基础版本的Dijkstra算法
voidDijkstra( Vertexs )
{
while(1){
V=未收录顶点中dist最小者;
if( 这样的V不存在 )
break;
collected[V] =true;
for( V的每个邻接点W )
if( dist[V] +E<v,w><dist[W] ){//Vd点的加入使我们得到一个更短的w的距离
dist[W] =dist[V] +E<v,w>;//更新距离
path[W] =V;//更新最短路径
}
}
}
根据基础进行改良过后的
最基础版本的Dijkstra算法
voidDijkstra( Vertexs )
{
while(1){
V=未收录顶点中dist最小者;
if( 这样的V不存在 )
break;
collected[V] =true;
for( V的每个邻接点W )
if( dist[V] +E<v,w><dist[W] ){//Vd点的加入使我们得到一个更短的w的距离
dist[W] =dist[V] +E<v,w>;//更新距离
path[W] =V;//更新最短路径，s走到V的所有费用加上V走到W这条边的费用
}
elseif((dist[V]+E<v,w>==dist[W]) && (cost[V] +C<v,w><cost[W])){//等长最短路径并且这条路径上面的新费用比原来的费用小的话那也要更新路径
cost[W] =cost[V] +C<v,w>;//更新费用
path[w] =V;//更新路径
}
}
}
图习题.2 其他推广
其他类似问题
- 要求最短路径有多少条?
- count[s] = 1;//计数器的作用
- 在要求数最短路径有多少条的问题中，如果找到更短路，则count[W]应该更新为要求边数最少的最短路：count[W]=count[V]
- 在要求数最短路径有多少条的问题中，如果找到等长路，则count[W]应该更新为：count[W]+=count[V]
- 要求边数最少的最短路
- 费用初始化怎么做？初始化为0
- count[s] = 0;
- 如果找到更短路：count[W] = count[V] + 1;
- 如果找到等长路：count[W] = count[V] + 1;//count[V]加上新的权重
