DIjkstra算法

DIjkstra算法

　　　一.算法思想

　　　　　　步骤如下：

　　　　　　1、选取一个起点s，设置一个int型数组（此处使用数组d）表示起点到各个点的最短距离，设置一个bool型数组（此处使用数组vis）表示每个点是否访问过

　　　　　　2、让起点到各个点的距离变为INF无限大（起点到自己的距离应该为0）

　　　　　　3、重复一下过程n次（n为顶点个数）

　　　　　　{

　　　　　　　　1、在所有未访问的节点中选取到达其最短路最短的那一个（其实就是找一个d数组中最小并且为访问的）

　　　　　　　　2、把它标记为访问过

　　　　　　　　3、把所有与它相连的点更新

　　　　　　}

　　　　　eg.要求在下图中找到从a到b的最短路

　　　　　　①：选取1作为起点，现在d数组是{0,INF,INF,INF,INF,INF}

　　　　　　②：通过1把与其相邻的点更新——————d数组变为{0,7,9,INF,INF,14}

　　　　　　③：选取下一个点——————2

　　　　　　④：通过2把与其相邻的点更新——————d数组变为{0,7,9,22,INF,14}

　　　　　　⑤：选取下一个点——————3

　　　　　　⑥：通过3把与其相邻的点更新——————d数组变为{0,7,9,20,INF,11}

　　　　　　⑦：选取下一个点——————6

　　　　　　⑧：通过6把与其相邻的点更新——————d数组变为{0,7,9,20,20,11}

　　　　　　⑨：选取下一个点——————4

　　　　　　⑩：通过4把与其相邻的点更新——————d数组变为{0,7,9,20,20,11}

　　　　　　 shi‘yi：选取下一个点——————4

　　　　　　⑩：通过4把与其相邻的点更新——————d数组变为{0,7,9,20,20,11}

　　　　　　…………

　　　　　　于是，Dijkstra的代码就可以很轻易地得出：