最短路径算法

最短路径算法在现实生活中也具有非常多的应用，例如在一个复杂的景区，想要从一个景点到另外一个景点，利用最短路径算法就可以找到最短的路程，而如果不做规划就随缘前往，可能会绕很多路才能到达，虽然到了，但是精力都花费在走路上了，更别说去观光景点了。

• Dijkstra算法：
  • 算法思想分析：
    算法从一个点开始，向周围扩散，每次去寻找一个确定了最短路径的点，并且同时更新所有点的最短路径距离，直到所有点都被找到最短路径
  • 算法具体代码：

#define MAX    100
#define INF    32767
int tempMatrix[MAX][MAX]; // 邻接矩阵
int mVexNum; // 顶点数量
void dijkstra(int start, int prev[], int dist[])
{
    int i,j,k = 0;
    int min;
    int tmp;
    int flag[MAX];      // flag[i] = 1 表示"顶点vs"到"顶点i"的最短路径已成功获取。
    
    // 初始化
    for (i = 0; i < mVexNum; i++)
    {
        flag[i] = 0;              // 顶点i的最短路径还没获取到。
        prev[i] = 0;              // 顶点i的前驱顶点为0。
        dist[i] = tempMatrix[start][i]; // 顶点i的最短路径为"顶点start"到"顶点i"的权。
    }
    
    // 对"顶点start"自身进行初始化
    flag[start] = 1;
    dist[start] = 0;
    
    // 遍历mVexNum-1次；每次找出一个顶点的最短路径。
    for (i = 1; i < mVexNum; i++)
    {
        // 寻找当前最小的路径；
        // 即，在未获取最短路径的顶点中，找到离start最近的顶点(k)。
        min = INF;
        for (j = 0; j < mVexNum; j++)
        {
            if (flag[j] == 0 && dist[j] < min)
            {
                min = dist[j];
                k = j;
            }
        }
        // 标记"顶点k"为已经获取到最短路径
        flag[k] = 1;
        
        // 修正当前最短路径和前驱顶点
        // 即，当已经知道"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
        for (j = 0; j < mVexNum; j++)
        {
            tmp = (tempMatrix[k][j] == INF ? INF : (min + tempMatrix[k][j]));
            if (flag[j] == 0 && (tmp  < dist[j]))
            {
                dist[j] = tmp;
                prev[j] = k;
            }
        }
    }
}

• 算法细节分析：
  算法中用到了三个数组，分别是：

  • prev [ ]：用来存储每个节点的前驱节点
  • dist [ ]：用来存储每个节点的最短路径距离
  • flag [ ]：辅助数组，用来存储每个节点是否已经找到了最短路径

  算法中用到了三次循环，分别是：

  • 第一次：循环了N-1次，目的是每次循环都找到一个节点的最短路径
  • 第二次：循环了N次，目的是找到目前距离起始点最近的点，然后标记为已经找到最短路径
  • 第三次：循环了N次，由于新加入了一个确定了最短路径的节点，那么原来的节点的最短路径将有可能被更新，所以这个循环的目的就是更新所有的节点的最短路径的距离，如果发现了更短路径，同时也会将前驱节点更新

  回首在最小生成树算法中的Prim算法，这两者的过程十分相似，那两者的差别点在哪里呢？

• 与Prim算法的相同点和不同点：

  • 相同点：
    1. prev [ ] 数组和flag [ ] 数组是一样的，在两个算法中均有一个用来存储前驱节点的数组，目的是为了在算法进行完之后将路径打印出来，另外一个用来存储每个节点是否被确定。
    2. 有两次循环是一样的，第一次循环都是为了每次确定一个点，最后一次循环，也都是因为有新的点被确定了，所以需要更新其他节点的状态
  • 不同点：
    1. 在Dijkstra算法中使用一个数组来存储每个节点的最短路径距离，而在Prim算法中使用一个数组来存储节点到最小生成树中的节点的最短距离
    2. 在Dijkstra算法中的第二个循环是来找目前离起始点最短距离的点，而在Prim算法中的第二个循环是用来找目前离最小生成树中的节点距离最近的点

• Floyd算法

  • 算法思想分析：
    Floyd算法的过程建立在一个矩阵中，这个矩阵存储的是各个点之间的距离，对于每个点进行一次循环，这个循环过程中做的事情就是去寻找通过该节点的边是否小于原本存储在矩阵中的值，如果小于，则更新
  • 算法的具体代码：

#define MAX    100
#define INF    32767
int mVexNum;             // 顶点数
int mMatrix[MAX][MAX];   // 邻接矩阵
void floyd(int path[][MAX], int dist[][MAX])
{
    int i,j,k;
    int tmp;
    
    // 初始化
    for (i = 0; i < mVexNum; i++)
    {
        for (j = 0; j < mVexNum; j++)
        {
            dist[i][j] = mMatrix[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
            path[i][j] = j;                // "顶点i"到"顶点j"的最短路径是经过顶点j。
        }
    }
    
    // 计算最短路径
    for (k = 0; k < mVexNum; k++)
    {
        for (i = 0; i < mVexNum; i++)
        {
            for (j = 0; j < mVexNum; j++)
            {
                // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
                tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
                if (dist[i][j] > tmp)
                {
                    // "i到j最短路径"对应的值设，为更小的一个(即经过k)
                    dist[i][j] = tmp;
                    // "i到j最短路径"对应的路径，经过k
                    path[i][j] = path[i][k];
                }
            }
        }
    }
}

• 算法的细节分析：
  算法中用到了两个数组：

  • dist [ ]：这个二维数组用来存储两个节点之间的最短路径距离
  • path [ ]：这个数组用来存储两个节点之间的最短路径将会经过的点，目的是用来存储最短路径

  算法中用到了三次循环：

  • 第一次循环：第一次循环N次，对于每个点都需要进行更新表的操作
  • 第二次循环和第三次循环：这两次循环实际上是对矩阵的一个遍历操作