最短路径问题是图研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：

• 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。

• 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

• 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。

• 全局最短路径问题 - 求图中所有的最短路径。

Dijkstra算法

算法思想

Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法。
首先，我们引入一个辅助向量D，它的每个分量D[i]表示当前找到的从起始节点v到终点节点vi的最短路径的长度。它的初始态为：若从节点v到节点vi有弧，则D[i]为弧上的权值，否则D[i]为∞，显然，长度为
D[j] = Min{D[i] | vi ∈V}
的路径就是从v出发最短的一条路径，路径为(v, vi)。
那么，下一条长度次短的最短路径是哪一条呢？假设次短路径的终点是vk，则可想而知，这条路径或者是(v, vk)或者是(v, vj, vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的权值之和。

一般情况下，假设S为已知求得的最短路径的终点集合，则可证明：一下条最短路径（设其终点为x）或者是弧(v, x)或者是中间只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明，假设此路径上有一个顶点不在S中，则说明存在一条终点不在S中而长度比此路径短的路径。但是这是不可能的。因为，我们是按路径常度的递增次序来产生个最短路径的，故长度比此路径端的所有路径均已产生，他们的终点必定在S集合中，即假设不成立。

因此下一条次短的最短路径的长度是：
D[j] = Min{D[i] | vi ∈ V - S}
其中，D[i]或者是弧(v, vi)的权值，或者是D[k](vk ∈ S)和弧(vk, vi)上权值之和。

代码实现

/// 最短路径 - Dijkstra 算法
/// @param G 网图
/// @param v0 开始的顶点
/// @param P 前驱顶点下标
/// @param D 表示从V0到V的最短路径长度和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D) {
    int v, w, k, min;
    k = 0;
    int final[MAXVEX];
    
    for (v = 0; v < G.numVertexes; v++) {
        final[v] = 0;
        (*D)[v] = G.arc[v0][v];
        (*P)[v] = 0;
    }
    
    final[v0] = 1;
    (*D)[v0] = 0;
    (*P)[v0] = -1;
    
    for (v = 1; v < G.numVertexes; v++) {
        min = INFINITYC;
        for (w = 0; w < G.numVertexes; w++) {
            if (!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];
            }
        }
        
        final[k] = 1;
        
        for (w = 0; w < G.numVertexes; w++) {
            if (!final[w] && min + G.arc[k][w] < (*D)[w]) {
                (*D)[w] = min + G.arc[k][w];
                (*P)[w] = k;
            }
        }
    }
}

Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

算法思路

1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

代码实现

void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) {
    int v, w, k;
    for (v = 0; v < G.numVertexes; v++) {
        for (w = 0; w < G.numVertexes; w++) {
            (*D)[v][w] = G.arc[v][w];
            (*P)[v][w] = w;
        }
    }
    
    for (k = 0; k < G.numVertexes; k++) {
        for (v = 0; v < G.numVertexes; v++) {
            for (w = 0; w < G.numVertexes; w++) {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];
                }
            }
        }
    }
}