迪杰斯特拉（Dijkstra)

心血潮来，想写一篇关于迪捷斯特拉算法的文

迪捷斯特拉算法适合求单源最短路径的问题，例如给你一个图，要你算出某一个起点s,到其他任一点e的最短路径。Dijkstra有人说是贪心，有人说是dp,有人说是弱化版本的bfs,如果想知道原理的小伙伴建议去看算法导论的证明部分~

如图所示，现在我们要求从v0----- 图中任意一个节点的最短路径。

算法思路：首先建立一个数组int d[Max], 这个数组的含义是起点s到其他点的最短距离,最后我们如果把这个数组求出来了，很显然d[i],就是起点s到Vi的最短距离了，假设我们的起点是s,那么d[s]=0,自身到自身的距离为0，其他点我们设置为一个特别大的数字1000000,表示很远的距离

接着，进入循环，我们每次从d[]这个数组中找到距离s最小的数：d[u]，然后看一下u到其他没有访问过的节点的距离G[u][i]+d[u]是否小于d[i]这个值，如果小于就更新这个值使得d[i]=G[u][i]+d[u]，如果不小于，就不用更新了，一直这样循环下去直到所有的节点被访问~

最初的d数组

如图所示，我们寻找d[i]的最短的一个，很显然是v0，将其标记为以访问,并将这个中介点设置为u，这时的u为v0然后去寻找有没有一个没有访问过的点使得G[u][i]+d[u],有三个需要更新的值，那就是d[v4],d[v3],d[v1],因为他们最初的时候都是无穷大。
更新d数组

更新完毕以后

再次从d这个数组中找到一个最小值u,然后将其标记

寻找剩下没有访问过的节点使得G[u][i]+d[u]的值小于dp[i]，并更新其值

很显然，我们发现d[u]+G[u][3]比dp[3]要小，我们更新其值，更新后数组为：

重复上面的步骤，再次从d[i]中未访问的节点中取出一个最小的，

标记后，重复上面的步骤，u开始讯号其他未访问的节点，有没有一个节点i，使得d[i]<G[u][i]+d[u],此时v4不满足，v2满足，我们更新一下数组的值

继续寻找最小值,此时d[v4]最小，标记

重复上面的步骤，更新数组的值~

继续寻找最短距离,此时未v2,标记

重估上面步骤,更新数组的值

继续寻找最小值

至此全部访问完毕~~

数组d中的值就是源点s到各个点的最短距离~