dijkstra算法可以求一个点到其他所有点的最短路径。

步骤：

初始化距离数组,dist[i]表示i到1的最短距离。s:表示当前已确定最短距离的点

dist[1]=0，dist[i]=+inf

for i in 0~n:

(1)t<----不在s中距离最近的点?

(2)t加入s,用t更新其他所有点的距离。

思考:

定理最短路径的子路径仍然是最短路径和dij算法有什么关系?

    为了证明松弛操作的合理性，如果从源点到某个顶点存在一条比现在源点到该顶点最短路径还短的路径，那么就必须要更新这个最小值。

为什么每次迭代后，s中的顶点对应的dist值就是最短距离，一个顶点一旦加到S中，其最短路径不再改变是为什么？

    第一次迭代后，源点加入s，结论成立。假设第k-1次迭代后s中顶点最短路径是dist数组中的值，第k次迭代要要找s外距离源点最短的点，并对所有点进行松弛操作。

为什么每次迭代找S外距离源点最短的点这个距离就是最短的，可不可能出现一个更短的距离呢？

   不可能。第k次迭代S外距离源点最短的点为j，j在前k-1次迭代的时候就进行过松弛操作，而s外的点除j外到源点的距离都比j大，所以不可能出现经过s外点到j的最短路径，所以第k次迭代dist[j]就是源点到j的最短路径。

dij算法和贪心算法有什么关系？

   dij算法每次把s外距离源点的最小值加入s中(这个距离就是源点到该点的最短距离)，这是贪心算法。使用这个点来进行松弛操作(命题)，来更新S外点到源点的最短距离。