建设保障房网站首页,网络营销网站建设论文,滨州网站建设哪家专业,wordpress 免费主机最短路径问题 单源最短路径Dijkstra算法原理代码实现 Bellman-Ford算法原理代码实现SPFA优化SPFA代码实现 多元最短路径Floyd-Warshall算法原理代码实现 单源最短路径
#x1f680;最短路径#xff1a;从图G的某个顶点出发到达另一个顶点的最短路径#xff0c;其中最短是指… 最短路径问题 单源最短路径Dijkstra算法原理代码实现 Bellman-Ford算法原理代码实现SPFA优化SPFA代码实现 多元最短路径Floyd-Warshall算法原理代码实现 单源最短路径
最短路径从图G的某个顶点出发到达另一个顶点的最短路径其中最短是指路径上边的权值和最小。 单源最短路径从图G中的某一顶点出发到达其余顶点的最短路径。
Dijkstra
算法原理
针对一个带权有向图将所有的顶点划分为两个集合S和QS是已经确定最短路径的顶点结合Q是还未确定最短路径的顶点集合。每次从Q中找出一个从起点s到达该结点代价最小(权值和最小)的结点u(可见迪杰斯特拉算法同样采取的是贪心策略)将u从集合Q中移除并放入S中对u所邻接的顶点做一次松弛操作。松弛操作即对结点u的邻接点v判断从起点s到u的代价u到v的代价是否小于s到v的代价若小于那么对s到v的代价替换为s到u的代价u到v的代价。这样依次从Q中选出结点u直到Q为空为止。
算法特点比较与其他最短路径的算法迪杰斯特拉算法的效率较优。但是此算法只能用于没有负权值的图。 源点为s即求s到达其他顶点的最短路径。在初始时s到达其他边的路径长度均为无穷大 到达自身的距离为0。 算法执行过程 代码实现
void Dijkstra(const V src, std::vectorW dist, std::vectorint parent_path) {//初始化工作size_t n _vertex.size();size_t srci this-GetVertexIndex(src);dist.resize(n, W_MAX);dist[srci] 0;parent_path.resize(n, -1);std::vectorbool S(n, false); //已选出的顶点集合Sfor (size_t i 0; i n; i) {//从dist中选出最短的一条边S-usize_t u -1;W min_eg W_MAX;for (size_t j 0; j n; j) {if (dist[j] min_eg false S[j]) {u j;min_eg dist[j];}}//将这个顶点添加到S集合中S[u] true;//更新从起始点srci能够到达的其他点的最短路径dist数组for (size_t i 0; i n; i) {if (_matrix[u][i] ! W_MAX false S[i] dist[u] _matrix[u][i] dist[i]) {dist[i] dist[u] _matrix[u][i];parent_path[i] u;}}}
}dist数组和parent_path数组解释将源点s到达其他顶点的最短路径数值存储在dist数组中dist[i]即为源点s到达i号顶点的最短距离。parent_path数组用来记录源点s到达其他顶点的最短路径采用的是双亲表示法即该结点存储的内容为源点s到达这个结点路径上的上一个结点的下标。
上面例子中最终两个数值的内容如下 Bellman-Ford
算法原理
迪杰斯特拉算法不能解决带负权值路径的情况贝尔曼算法可以解决这一问题。相比于迪杰斯特拉的贪心策略贝尔曼算法是一种较为暴力的解法即对每一个结点都做一次松弛操作但是一轮松弛操作往往不能得到最终结果存在最短路径于最短路径权值和对应不上的情况所以要经过多轮更新才能得到最终结果。最多轮次为n-1轮(n:顶点个数)如果说第n轮更新还能有顶点松弛成功说明存在权值和为负数的环路情况这种情况贝尔曼算法也是解决不了的(权值和为负数的环路意味着每轮更新都能得到一个更小的结果是无休止的)。
只经过一轮更新不能的到最终结果的例子 产生上图中这样结果的原因在于更新源点s到达z顶点的最短路径是由对t顶点的邻接顶点做松弛操作得到的但是在更新源点s到达z的最短路径之后在对x的邻接顶点做松弛操作的时候又重新修改了源点s到达t顶点的最短路径此时在parent_path数组中t位置的数据修改成了x的下标同样也因此导致了s到达z顶点的路径于路径上的权值和不一致的情况。所以要对t的邻接顶点重新做一次松弛操作上面这种情况再对t的邻接顶点做一次松弛操作就可以解决问题但是对于其他更为复杂的问题可能仍旧需要新一轮的松弛操作。那么松弛操作轮数的上限是多少次呢n - 1次因为源点出发到达另一个顶点的最短路径至多经过n - 1条边所以至多经过n - 1轮的更新就能得到最终结果但是如果第n轮时仍旧存在到达某个点的最短路径发生了更新那么就说明存在权值和为负数的环路问题。 代码实现
bool Bellman(const V src, std::vectorW dist, std::vectorint parent_path) {//初始化结构size_t n _vertex.size();size_t srci this-GetVertexIndex(src);dist.resize(n, W_MAX);dist[srci] 0;parent_path.resize(n, -1);//寻找最短路径for (size_t k 0; k n - 1; k) {bool update false;//update小的优化--如果此轮更新中没有任何一条边松弛成功此时就可以break退出std::cout 第 k 1 轮更新: \n;for (size_t i 0; i n; i) {for (size_t j 0; j n; j) {if (_matrix[i][j] ! W_MAX dist[i] _matrix[i][j] dist[j]) {update true;dist[j] dist[i] _matrix[i][j];std::cout i - j : dist[j] std::endl;parent_path[j] i;}}}if (false update) {break;}}//如果经过n-1轮还能进行更新说明出现了负权值环路问题for (size_t i 0; i n; i) {for (size_t j 0; j n; j) {if (_matrix[i][j] ! W_MAX dist[i] _matrix[i][j] dist[j]) {return false;}}}return true;
}SPFA优化
在上面分析一轮的松弛操作可能不能得到最终结果的问题时解决方案就是再对t顶点的邻接顶点做一次松弛操作即可并不用再对其他顶点做一次松弛操作也就是说如果要在下一轮中再次对某个顶点的邻接顶点做松弛操作那么这个顶点一定在本轮中得到了最短路径的更新否则其不会对其他顶点产生影响。
SPFA算法就是对上面代码中写的贝尔曼算法的一个优化就是说如果要在下一轮中再次对某个顶点的邻接顶点做松弛操作那么这个顶点一定在本轮中得到了最短路径的更新所以在第一轮更新中所有顶点都需要更新把所有的顶点都入队列在后续的更新中如果某个顶点在本轮没有被更新那么其也不会对其他顶点产生影响就不用再次入队列相反需要再次入队列 这样循环置队列为空即可。
SPFA代码实现
void BellmanSPFA(const V src, std::vectorW dist, std::vectorint parent_path) {//初始化结构size_t n _vertex.size();size_t srci this-GetVertexIndex(src);dist.resize(n, W_MAX);dist[srci] 0;parent_path.resize(n, -1);std::queuesize_t q;std::vectorbool flag(n, false);q.push(srci);flag[srci] true;while (!q.empty()) {size_t top q.front();q.pop();flag[top] false;for (size_t i 0; i n; i) {if (_matrix[top][i] ! W_MAX dist[top] _matrix[top][i] dist[i]) {dist[i] dist[top] _matrix[top][i];parent_path[i] top;if (flag[i] false) {q.push(i);flag[i] true;}}}}
}多元最短路径
Floyd-Warshall
算法原理
佛洛依德算法是一个解决多源的最短路径问题的经典算法它能够计算出每个顶点到达其余顶点的最短路径对应用场景通常是带负权值的多源最短路径问题。
佛洛依德算法采用的是动态规划的思想顶点i到达顶点j的最短路径上至少经过了0个其他顶点至多经过了n - 2个其他顶点其状态标识可以定义为dp[i][j][m]标识顶点i到达顶点j的最短路径上经过了k个其余顶点其余顶点就是除了起始顶点和终止顶点的其他顶点记作k(k有n-2种取值可能)所以如果i到j的最短路径经过k那么dp[i][j][m] dp[i][k][m-1] dp[k][j][m-1]如果i到j的最短路径不经过kdp[i][j][m] dp[i][j][m-1]所以最终dp[i][j][m] min(dp[i][j][m-1],dp[i][k][m-1]dp[k][j][m-1])。在正常写代码时通常将其优化为二维的动态规划因为第三维的m总是依赖于m-1的。
代码实现
void Floyd(std::vectorstd::vectorW dist, std::vectorstd::vectorint parent_path) {//初始化结构size_t n _vertex.size();dist.resize(n);parent_path.resize(n);for (size_t i 0; i n; i) {dist[i].resize(n, W_MAX);parent_path[i].resize(n, -1);}//初始化直接相连的边for (size_t i 0; i n; i) {for (size_t j 0; j n; j) {if (_matrix[i][j] ! W_MAX) {dist[i][j] _matrix[i][j];parent_path[i][j] i;}if (i j) {dist[i][j] 0;}}}//动态规划for (size_t k 0; k n; k) {for (size_t i 0; i n; i) {for (size_t j 0; j n; j) {if (dist[i][k] ! W_MAX dist[k][j] ! W_MAX dist[i][k] dist[k][j] dist[i][j]) {//更新dist[i][j] dist[i][k] dist[k][j];parent_path[i][j] parent_path[k][j];}}}}
}
