最短路径

在网图和非网图中，最短路径的含义是不同的。对于非网图，由于其边上没有权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径。而对于网图，最短路径，是指两顶点之间经过的边上权值之和最少的路径。

和最小生成树的区别：

最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。

最短路径是从一点出发，到达目的地的路径最小。

Prim 和 Dijkstra 代码非常相似，都是这样一个大体步骤：初始化，找最小值，更新权值数组。注意对比他们的代码。

迪杰斯特拉算法(Dijkstra)

按路径长度递增的次序产生最短路径。

一步一步求出他们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

#include "邻接矩阵.h"
#define MAXVEX 9
#define INF 65535
typedef int Patharc[MAXVEX];
typedef int ShortPathTable[MAXVEX];
void
Dijkstra(MGraph G, int begin, Patharc *P, ShortPathTable *D)
{
    /*
    ShortPathTable数组 表示 begin 到 某顶点的"最短路径和"
    Patharc数组 比如P[v] = w，表示 v的前驱为w
    */
    int v, w, k, min;/*k用来存放最小值min对应的顶点下标*/
    int final[MAXVEX]; /*存放begin 到 某顶点 是否已经求得最短路径，如果begin到v2已经求得，final[2] = 1*/
    for(v = 0; v < G.numVertexes; v++)
    {
        final[v] = 0; /*所有顶点都未求得最短路径*/
        (*D)[v] = G.arc[begin][v];
        (*P)[v] = -1;/*这里书上是0，是错误的，更正为-1后，每当一个结点的前驱为-1，即等同于它的前驱为begin
        如初始化第一次还是计算从begin到各顶点的权值。如果D[v] = 3;P[v] = -1; 就表示从begin到v的最短路径和为3； 
        */
    }
    (*D)[begin] = 0; /*起始点到起始点的路径为0，如果对角线用INF表示这行代码是必须的，如果用0表示对角线，这行代码多余*/
    final[begin] = 1;/*起始点到起始点不需要求路径*/

    /*初始化结束 开始循环生成最短路径*/
    for(v = 1; v < G.numVertexes; v++)
    {
        /*这里为什么循环是从1开始的，因为顶点begin已经再=在最短路径中，不需要再求*/
        /*寻找D数组中没有被纳入Final数组的部分的最小值*/
        min = INF;
        for(w = 0; w < G.numVertexes; w++)
        {
            if(!final[w] && (*D)[w] < min)
            {
                k = w;
                min = (*D)[w];
            }
        }
        final[k] = 1;
        /*找到最小值，相应下标顶点纳入final数组，=1表面该顶点已经在最小路径中。*/
        /*更新从begin到各未被纳入顶点的值，如果小于先前的最小路径和，就更新，并把顶点的前驱在P数组中置为之前求得的k，这里有这样一个对应关系*/
        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;
            }
        }
    }
}