无权图的最短路径用BFS来求

void shortestPath_BFS(Vertex s)
{
    Queue<Vertex> q;
    for each Vertex v
        v.dist=∞;
    s.dist=0;    q.enqueue(s);
    while(!q.isEmpty())
    {   
        Vertex v=q.dequeue();
        for each Vertex w adjacent to v
            if(w.dist==∞)
            {
                w.dist=v.dist+1;
                w.path=v;
                q.queue(w);
             }
    }
}

O(|V|+|E|)

---

有向带权图
两点之间的最短路径也包含了路径上其他顶点间的最短路径。

Dijkstra算法求单源最短路径

没有负权值
s[]记录已求得最短路径的顶点，初始化是将s[源点]置为1，其余为0
dist[]记录从源点v0到其他各顶点当前的最短路径长度，dist[i]的初值为arcs[v0][i]
path[]记录从源点到顶点i之间最短路径的前驱结点
在未求得最短路径的顶点中选取dist最小的点vj，将其s置为1，更新邻接点中未被求得最短路径的点的dist若可以更小就更新且还要更新path为vj，在重复找dist最小的，直到所有点的s都为1
pic
时间复杂度O(|V|^2)
要找出所有结点对之间的最短路径，需对每个结点使用一次Dijkstra，时间复杂度为O(|V|^3)
注意
边上带有负权值时，该算法并不适用，破坏了当前最近的点的最短路径上不可能会有其它当前距离比它远的点，因为权值是正的话只会越加越大。

边带有负权值.PNG

---

Floyd算法求各顶点之间最短路径

基本思想是一步步减小距离
采用矩阵D[|V|][|V|]来存储两点之间最小距离
D^k[i][j]=路径{i->{l<=k}->j}的最小长度（中途仅经过编号小于等于k的点）
D^{-1（权值矩阵），D}0，D^1，D(|V|-1)逐步得到最短距离
当加入某个新的点，即又增加了一个可经过的点，若使i，j之间的距离减小了的话则更新。
当D^(k-1)已经完成时，递推如下
1.k不属于最短路径{i->{l<=k}->j}，则D^k=Dk-1
2.k属于最短路径{i->{l<=k}->j}，则该路径必定是由两段最短路径组成
D^k[i][j]=D(k-1)[i][k]+D^(k-1)[k][j]
就是如果D^{(k-1)[i][k]+D}(k-1)[k][j]比D^(k-1)[i][j]更小的话就更新咯

vois ShortestPath_FLOYD(MGraph G, PathMatrix &P[], DistanceMatrix &D)
{
    for(v=0;v<G.vexnum;++v){
        for(w=0;w<G.vexnum;++w){
            D[v][w]=G.arc[v][w];
            for(u=0;u<G.vexnum;++u)
                P[v][w][u]=FALSE;
            if(D[v][w]<INFINITY){
                P[v][w][v]=TURE;
                P[v][w][w]=TRUE;
         }
    }
    for(u=0;u<G.vexnum;++u){
        for(v=0;v<G.vexnum;++v){
            for(w=0;w<G,vexnum;++w){
                if(D[v][u]+D[u][w]<D[v][w]{
                     //找到了一条更短的路径
                    D[v][w]=D[v][u]+D[u][w];
                    //v到w的路径为v到u和u到w的路径的组合
                    P[v][w][i]=P[v][u][i]||P[u][w][i];
                }
            }
        }
    }
}

时间复杂度O(|V|^3) 适合稠密图
允许图中带有负权值的边，但不允许有包含带负权值的边组成的回路
同样适用于带权无向图，因为可看作有往返二重边的有向图