5.5 最短路径

1. Dijkstra算法（迪杰斯特拉算法）

所求的是，某一个顶点到图中各点的最短路径。
算法基本思路

1. 找到离顶点最近且未标记的点，此时所得的路径便是这两点最短的距离（当前两点路径已经是全图最近，若再经过别的点的中转，必然绕远了）
2. 标记最近点
3. 刷新所有点离开始顶点的距离，重复第一步

for (v = 0; v < G.numVertexes; y++)
{
    //初始化各点与源点的距离，final用于保存各点是否找到最短路径
    final[v] = 0;
    D[v] = G.matirx[V0][v];
    P[v] = 0;
}
//
for (v = 1; v < G.numVertexes; v++) 
{
    //遍历所有结点，找到离源点最近，且还未找到最短路径的点
    min = INFINITY;
    for (w = 0; w < G.numVertexes; w++)
    {
        if (!final[w] && D[w] < min)
        {
            k = w;
            min = D[w];
        } 
     }

    final[k] = 1;//把顶点k标记，已经找到最短路径
    for (w = 0; w < G.numVertexes; w++)
    {
        //k点最短路径找到后，更新没找到最短路径的顶点与源点的距离
        if( !final[w] && (min + G.matirx[k][w] < D[w]))
        {
            D[w] = min + G.matirx[k][w];
            P[w] = k;
        }
    }
}

2. Floyd算法（弗洛伊德算法）

不断地通过尝试添加中转点，刷新两个顶点之间的距离，保存最短的。最终找到所有顶点到所有顶点的最短路径。

为此，需要两个变量用以保存，一个是两点之间的距离，一个是两点之间离终点最近的一个中转点。

for (v = 0; v < G.numVertexes; ++v)
{
    for (w = 0; w < G.numVertexes; ++w)//遍历所有顶点对
    {
        D[v][w] = G.matirx[v][w];//两点距离，初始化为邻接矩阵的距离
        P[v][w] = w;//路径直接保存为w
    }
}

for (k = 0; k<G.numVertexes; ++k)
{
    for (v = 0; v < G.numVertexes; ++v)
    {
        if ( D[v][w] > D[v][k] + D[k][w])  
        {
            //如果新的中转点使得两点距离变短，更改两点距离及路径
            D[v][w] = D[v][k] + D[k][w];
            P[v][w] = k;
        }
    }
}