dijkstra【未优化】

S_Gloria · 2019-08-10 18:17:13 · 个人记录

就想学习一下陈老师的讲课思路：

dij算法核心就是贪心思想，可以建立两个集合：

一个是已经可以确定，不会被其他点松弛的点集，另一个是未知是否能被更新的点集，用已知去更新未知。

如上图所示，

int u=1;//源点u为1 
memset(dis,88,sizeof(dis));
dis[1]=0;//1到本身的距离为0 

所以1肯定是已知dis。

距源点最短的点3，加入已知集合。 以此类推，即可求出dis数组。