图的算法
Dijkstra算法:(净化被黑暗能量污染的城市) 求图的单源最短距离,给出图G(V,E) (精灵城市图)和起点城市O (Origin),设置一个存放已经被光明之力净化的城市集合S,现在要从起点O出发,开放所有与起点O相连的road,以最短路径去往各城市进行净化,每次从V-S集合(未被净化的城市)中选出一个与起点城市O距离最近的城市Vi,选出Vi后就开放所有与Vi相连的road,从这些road计算看是否有可以优化起点城市到某城市Vj的最短路径(起点到Vi的最短路径距离+Vi—>Vj的road长度 是否小于 Vj 原本所记录的最短距离)(每个Vj 上记录了当前情况下起点到Vi的最短距离),如果小于则更新Vj上的数据,就这样每次从V-S集合(未被净化的城市)中选出一个与起点城市O距离最近的城市Vi 然后根据其road进行计算并优化,直到V-S集合为空。 有几个城市就设置循环几次,最终求出了起点O到所有城市的最短距离
可以用邻接矩阵和邻接表来实现该伪代码,邻接矩阵需要枚举所有顶点来查看Vj 是否可由Vi 到达,邻接表可以直接得到Vi 所有能到达的Vj
只能应对所有边权都是非负数的情况,边权出现负数最好适用SPFA算法
最外层for 循环n次是确保所有的节点都有被遍历到
找出最小的d[u]也要一个for循环n次,才能轮询找出最小值
优化d[u]也要一个for循环n次,确保能让所有的d[ ]都计算是否可以优化
**最短路径 ** :可以设置一个pre[v]来记录V节点的上一个节点,在每个优化d[v]后面加上pre[v]=u即可,可以通过递归将该路径输出
数组初始化一个特定数时用G[MAXV] [MAXV] ={INF}和 d[MAXV] = {INF}是不行的,无法全部初始化,要使用 fill (G[0],G[0]+MAXV*MAXV,INF)函数才行,fill (d,d+MAXV,INF)函数进行初始化。
总结
Dijkstra算法算是贪心思想实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。
标签:Vi,城市,MAXV,笔记,算法,road,Vj,起点 From: https://www.cnblogs.com/ywx1207/p/17863257.html