厦门最早做网站的公司,做视频的软件模板下载网站有哪些内容,wordpress主题跟目录,企业展厅设计公司西安文章目录 迪杰特斯拉算法主要特点基本思想算法步骤示例 实现迪杰斯特拉算法基本步骤算法思路 总结 迪杰特斯拉算法
迪杰特斯拉算法是由荷兰计算机科学家艾兹赫尔迪杰特斯拉#xff08;Edsger W. Dijkstra#xff09;在1956年提出的#xff0c;用于解决单源最短路径问题的经… 文章目录 迪杰特斯拉算法主要特点基本思想算法步骤示例 实现迪杰斯特拉算法基本步骤算法思路 总结 迪杰特斯拉算法
迪杰特斯拉算法是由荷兰计算机科学家艾兹赫尔·迪杰特斯拉Edsger W. Dijkstra在1956年提出的用于解决单源最短路径问题的经典算法。该算法的目标是从一个起始顶点找到到图中其他顶点的最短路径。
主要特点
适用于带权图其中权重为非负数。为什么只适用于非负数因为迪杰斯特拉的思想是贪心测量当有负权引入的时候贪心策略将不再适用解决从单个源点到其他所有顶点的最短路径问题。时间复杂度当使用优先队列例如堆时复杂度为 O ( E log V ) O(E \log V) O(ElogV)其中 V V V 为顶点数量 E E E 为边的数量。
基本思想
Dijkstra算法通过不断探索距离最近的顶点逐步扩展其最短路径的已知范围直到找到从源点到所有其他顶点的最短路径。该算法基于贪心策略每一步选择尚未处理的、距离源点最近的顶点进行扩展。
算法步骤 初始化 将起始顶点的距离设为0其余所有顶点的距离设为∞表示不可达。使用一个优先队列或最小堆来存储顶点及其当前的最短距离。 取距离源点最近的顶点并标记为已处理。 对于该顶点的每个邻接顶点更新其最短距离如果通过当前顶点可以获得更短的路径则更新距离。 重复步骤2和3直到所有顶点都被处理过或优先队列为空。
示例 实现迪杰斯特拉算法
基本步骤
首先假设我们有如下的一个图 灰色的点代表起点我们需要从起点开始算每个点到起点的最短路径。 第一步按照迪杰斯特拉的表述应该将起点到起点的最短路径初始化为0起点到另外其他点的距离初始化为正无穷。 这里我们更新完s点之后应该更新和s点相连的点的最短路径了由于之前s到t点和到y点的最短路径是正无穷由于st和sy都小于两个最短路径所以更新两个最短路径。 根据贪心策略更新出来的两个最短路径sy更小所以我们应该更新y相连的路径。 所以接下来我们应该更新y连接的点的最短路径。 由于原本s到t的最短路径是10但是现在的最短路径更新了之后是8所以更新结果由于之前s到x的最短路径是正无穷所以现在将最短路径更新为14s到z 也是相同的因为之前的最短路径是正无穷所以现在将最短路径更新为7. 在这三条最短路径中选择最短的那条 这里就应该以z为新的起点 更新z连接的顶点z一共有两条边一条是zs一条是zx由于s到s是最近的0所以这里不需要更新由于之前s到x的距离是14所以这里更新s到x的距离。 接下来再从剩下的边中选择最小的路径。 从t点开始只有一条路径所以这里t到xtx是1由于之前的st的最短路径是8所以此时的最短路径是9,913所以这里应该更新最短路径为9 这里最短路径算是更新完了。
算法思路
由于这里我们涉及到最短路径所以应该开辟一个dist数组我们来想一想一个dist数组是否能解决问题很显然是不能的我们还需要一个数组记录当前最短路径的前一个顶点的下标在遍历的时候我们可以索引每一个顶点了。 代码展示
void Dijkstra(const V src, vectorW dist, vectorint pPath)
{//获取起点的下标size_t srci GetVertexIndex(src);//确定节点的数量size_t n _vertexs.size();dist.resize(n, MAX_W);pPath.resize(n, MAX_W);//自己到自己的距离是0dist[srci] 0;//自己的前一个是自己pPath[srci] srci;//已经确定最短路径的顶点的集合vectorbool S(n, false);for(size_t j0;jn;j){//选择最短路径顶点且不在s中更新其他路径int u 0; //最小的那个点W min MAX_W; //最小权值for (size_t i 0;i n;i){if (S[i] false dist[i] min){//选出最小的点u i;//更新最小权值min dist[i];}}//u被选出来S[u] true;//松弛更新u连接出去的顶点v srci-u u-vfor (size_t v 0;v n;v){//确定u连接出去的所有边if (S[v] false _matrix[u][v] ! MAX_W (dist[u] _matrix[u][v]) dist[v]){dist[v] dist[u] _matrix[u][v];//将v的父亲更新为upPath[v] u;}}}
}打印路径节点和最短路径
//打印最短路径
void PrinrtShotPath(const V src, vectorW dist, vectorint pPath)
{//获取起点的下标size_t srci GetVertexIndex(src);//确定节点的数量size_t n _vertexs.size();for (size_t i 0;i n;i){if (i ! srci){// 先找出i顶点的路径vectorint path;size_t parenti i;//先将自己存进去(自己不是原点先push进去while (parenti ! srci){path.push_back(parenti);parenti pPath[parenti];}path.push_back(srci);//将路径逆置reverse(path.begin(), path.end());//打印出路径for (auto e : path){cout _vertexs[e] -;}//打印最短路径cout dist[i];cout endl;}}
}因为根据最后一个节点去推上一个节点推完之后数组中的节点会是一个反着的路径所以在打印的时候应该先把数组逆置逆置之后再进行打印。
总结
在本文中我们深入探讨了迪杰斯特拉算法的原理与应用。作为一种经典的最短路径算法迪杰斯特拉算法通过优先队列有效地解决了从单一源点到其他所有节点的最短路径问题。我们分析了其时间复杂度和空间复杂度了解了在不同图形结构下的性能表现。
通过示例和实现我们不仅掌握了算法的基本步骤还体验了其在实际应用中的重要性。无论是在交通导航、网络路由还是各种优化问题中迪杰斯特拉算法都发挥着不可或缺的作用。
希望本文能够帮助你更好地理解迪杰斯特拉算法并为你在图论和算法领域的进一步学习打下坚实的基础。如果你有任何疑问或想法欢迎在评论区与我交流
