框架建构¶

分为两大板块，单源最短路，和多源最短路。单源最短路就是求一个节点到其他节点的最短路。多源最短路是求任意两个节点的最短路距离。单源最短路，两大算法，Dijkstra和Bellman Ford.多源最短路，采用Floyd算法

单源最短路¶

Dijkstra 算法¶

概括性定义¶

在含有V个节点，E条边，边的权重非负的图中，求任意节点到start的最短路距离。采用邻接矩阵表示图。w[i][j]表示i到j的距离，若不可达，标记为Integer.MAX_VALUE.

思想与原理¶

在尚未确定的节点里，寻找最小的节点，将其确定,得到最终答案，然后用这个节点去服务其他节点，看是否可以通过这个点更新其他节点的最短路。

基本过程与代码实现¶

定义dist[i]表示i节点到start节点的最短路径的当前答案。解释：当前意味着还可被优化，还可被更新，等到无法更新的时候，意味着得到最终答案。
使用visited数组标记1个节点是否被访问，被访问意味着得到最终答案。
进行n次循环，每次寻找dist最小的点u，标记u为被访问，使用u来更新其他点。
1. 寻找dist最小的u,此时start到u的路径是已经被确定的。假设有其他节点v作为中转的新路径，那么新路径的距离是dist[v] + w[v][u].旧的路径距离是dist[u].比较可知，dist[v] > dist[u],且边权w[v][u]为正值。故假设不成立。这也解释了Dijkstra算法为什么不适用于负权图，如果是负权图，这一步寻找最小u，标记visited根本无法做到。
2. 使用u来更新其他点：要求通过start可到达u，并且通过u可到达待更新点m。对于m进行的具体操作是dist[m] = min(dist[m], dist[u] + w[u][m]).
每次循环都会让一个节点被访问，进行n次循环后，所有节点都被访问，所有节点的答案都得到确定，任务完毕。

简要的代码模板

//n次循环，每次找dist最小u,更新其他
for(int i = 0; i < n; i++){
    //比较dist数组，查找最小的u
    int u = min(dist);
    //标记u为被访问
    visited[u] = true;
    //利用u更新其他点
    for(int m : vertex){
        if(dist[u] != Integer.MAX_VALUE && w[u][m] != Integer.MAX_VALUE){
            dist[m] = Math.min(dist[m], dist[u] + w[u][m]);
        }
    }
}

复杂度分析与可供优化的点¶

假设有V个节点,E条边。时间复杂度是O(V^2).可以利用堆进行优化，将查找dist最小的这一步从n操作优化为logn操作。相应的，为了后续方便找到u可到达的节点，采用邻接表建图，便于访问。优化后的时间复杂度是O(ElogV)，每个点弹出一次，每次弹出是logv,所以这部分是O(VlogV).每更新一条边，就进行一次入堆，这部分O(ElogV),一般来讲，E>>V,故最终时间复杂度是O(ElogV)。