文章目录dijkstra算法详解(抖动算法) )简单易懂一、概要(百度百科)、算法思想和原理三、具体步骤四、动态展示五、一般代码实现(以相邻矩阵为例)六、扩展
详细的dijkstra算法(抖动算法)~~容易理解
PS：此算法不能用于求负权图，要求所有边的权重都为非负值。
一、简介(百度百科)抖动算法(Dijkstra )是荷兰计算机科学家sddj于1959年提出的，又称sddj算法。 这是从一个顶点到其余各顶点的最短路径算法，解决了权利图上的最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止
二、算法思想和原理dijkstra算法思想基于贪婪算法思想。 假设3358www.Sina.com/最优解，则重复到最后一个回合时得到的是所谓贪心算法即始终保持当前迭代解为当前最优解。意思就是在已知的条件下或是当前拥有的全部条件下保证最优解，若在此后的迭代中由于加入了新的条件使得产生了更优解则替代此前的最优解。通过不断的迭代不断保证每次迭代的结果都是当前。全局最优解降低了总体工作的复杂性，因为下一次迭代引用上一回合的最佳解。
在最短路径问题中，是局部最优解每一轮的迭代的工作量基本一致或在当前已知条件下从起点到其余各点的最短距离。 关键是已知条件，这也是Dijkstra算法最精妙的地方。 让我来说明一下。
戴克斯特拉方法假设初始集合，即初始条件中不存在顶点，即所有顶点之间不存在路径，即所有顶点之间的距离无限大。 那么，开始添加新条件。 由于已知源点和源点之间的距离最小，因此添加源点和源点的边缘，即当前的最短路径。 重复上述操作，直到所有顶点都添加到已知条件集。
三、具体步骤选择起点和终点结束； 所有点都添加到未知集合中(起点除外)，起点添加到已知集合中。 也就是说，这意味着到标志位为真，并确定了从该点到源点的最短路径。 初始化计算，更新起点和其他各点的成本dis (开始，n )； 在未知集合中，选择dis (开始，n )中值最小的点x，并将x添加到已知集合中。 在剩下的顶点，计算dis(start，n ) dis(start，x ) dis (x，n )
如果为真，则为dis(start，n )=dis ) start，x (dis ) x，n )，此时start和n点的路径通过x点。 循环直到goal点被添加到已知列表中，获取dis (开始，goal )是最短距离。 四.动态展示
五、一般代码实现(以相邻矩阵为例，基本数据const int inf=0x3f3f3f3f； //表示无限大。 常数上限=100； //最大顶点数int n，m； //n个顶点，m条边。 bool visited[maxn]； //判断是否确定到源点的最终最短距离。 int graph[maxn][maxn]； //权利地图int dis[maxn]； //从顶点到源点的最短距离。 int start，goal； //起点和终点。 初始化voidinit(memset ) visited，false，sizeof ) visited )； for(intI=1； i=n； I ) {dis[i]=graph[start][i]； 初始化//dis数组。 }} dijkstra算法的核心void dijkstra () /源点是源点start。 int minn； //记录各匝最短路径中最小的路径值。 int pos； //记录与得到的minn对应的下标。 init (； //调用初始化函数。 visited[start]=true； for(intI=1； i=n； I )//n个顶点按顺序添加到判断中。 minn=inf； for(intj=1； j=n； j () if (！ 已查看[ j ] dis [ j ] Minn ({ Minn=dis [ j ]； pos=j； //经过这个for循环我们找到的是我们想要的，可以确定从这个点到源点的最终最短距离。 可视[ pos ]=true； //我们将这一点合并到已知集合中。 //接下来是dis数组的更新。 也就是说，是现在的最短距离。 这是针对尚未合并到已知集合中的点。 for(intj=1； j=n； j () if (！ 可视[ j ] dis [ j ] dis [ pos ] graph [ pos ] [ j ] (dis [ j ]=dis [ pos ] graph [ pos ] [ j ] )； //退出循环后，所有点都合并到已知集合中，得到的dis数组为最终的最短距离。 coutdis[goal]endl； //从目标到源点的最短路径长度。 }主函数和头文件等# include bits/stdc.husingnamespacestd； int main () while(cinnm ) memset ) graph，inf，sizeof ) graph )； int u、v、w； for(intI=0； im； I ) {cinuvw； //graph[u][v]=w； //有向图graph[u][v]=graph[v][u]=w； //无有向图}cinstartgoal； //输入起点和终点。 dijkstra (； }返回0； (六、一旦学好dijkstra，恭喜你成功突破。 但是，未优化的dijkstra算法的时间复杂度为o(n2 ) o ) n^2) o(n2 )，如果存在顶点多边少等卡邻接矩阵问题，建议学习dijkstra的优化版详细内容请参照Dijkstra算法优化~~你一定会明白的4种高级优化