7.7 最短路径

7.7 最短路径

上节我们探讨了最小生成树的生成方法,分别是prim算法和Kruskal算法,这节课我们来探讨下求最短路径的算法

上上节我们探讨了广度优先和深度优先,其实这与本节有一定的关系

7.7.1 Dijkstra算法

1.什么是Dijkstra算法?

用于计算一个结点到其他结点的最短路径

算法的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想), 直到扩展到终点为止,不断地找最小值的点中的连线

2.图解

KBYanO.png

其实就是不断找最短的距离,要和之前的比较

3.算法

final数组为已求最短路径的顶点集合D数组为起点到各顶点的最短路径的权值和P数组为最短路径的路径的顶点

/* Dijkstra算法, 求有向网 G 的 v0 顶点到其余顶点 v 最短路径 P[v] 及带权长度 D[v], P[v] 的值为前驱顶点下标,
 * D[v] 表示 v0 到 v 的最短路径长度和 */
void ShortestPath_Dijkstra(MGraph G, int v0, ShortPathTable *D, Patharc *P)
{
    int min, k, final[MAXVEX];  /* final[w] = 1 表示求得顶点 v0 至 vw 的最短路径 */
    for(int v = 0; v < G.numVertexes; v++)  /* 初始化数据 */
    {
        final[v] = 0;     /* 全部顶点初始化为未知最短路径状态 */
        (*D)[v] = G.arc[v0][v];   /* 将与 v0 顶点有连线的顶点加上权值 */
        (*P)[v] = -1;     /* 初始化路径数组 P 为 0 */
    }
    final[v0] = 1;   /* v0 至 v0 不需要求路径 */
    (*D)[v0] = 0;    /* v0 至 v0 路径为 0 */

    /* 开始主循环, 每次求得 v0 到某个 v 顶点的最短路径 */
    for(int v = 1; v < G.numVertexes; v++)
    {
        min = INF;   /* 当前所知离 v0 顶点的最近距离 */
        for(int w = 0; w < G.numVertexes; w++)   /* 寻找离 v0 最近的顶点 */
        {
            if(!final[w] && (*D)[w] < min)
            {
                min = (*D)[w];    /* w 顶点离 v0 顶点更近 */
                k = w;
            }
        }
        final[k] = 1;   /* 将目前找到的最近的顶点置为 1 */
        //这里是更新最短路径长度
        for(int w = 0; w < G.numVertexes; w++)   /* 更新当前最短路径及距离 */
        {
            /* 如果经过 v 顶点的路径比现在这条路径的长度短的话 */
            if(!final[w] && (min + G.arc[k][w]) < (*D)[w])
            {
                /* 说明找到了更短的路径, 修改 D[w] 和 P[w] */
                (*D)[w] = min + G.arc[k][w];   /* 修改当前路径长度 */
                (*P)[w] = k;
            }
        }
    }
}

4.如果还想知道v3到v5这样任意顶点开始的最短路径怎么办?

对每个顶点作为源点运行一次上述算法

时间复杂度是O(n3)

7.7.2 Floyd算法

1.什么是Floyd算法

在给定的加权图中求最短路径的算法,其实就是不断尝试借助中间结点,而不是之间一步到位的结点,来求最短路径

2.核心是什么?

KBU3NQ.jpg

3.步骤是什么?

  1. 首先明确定义,定义两个二维数组D[MAXVEX][MAXVEX]P[MAXVEX][MAXVEX]D数组代表顶点到顶点的最短路径权值和矩阵, P代表对应顶点的最小路径前驱矩阵
  2. 初始的时候,将矩阵D中顶点D[v][w]设置为顶点v到顶点w权值,若两顶点不相连,则D[v][w] = INF
  3. 接下来对矩阵D更新, 如果D[v][w] > D[v][k] + D[k][w]k表示v、w`两顶点通过中转顶点,该表达式表示通过中转顶点的权值和较小时,更新v、w权值和

KBa3qK.png

4.算法是什么?

结构

#define MAXVEX 9
#define INF 65535
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

算法:

/* Floyd 算法, 求网图 G 中各顶点 v 到其余顶点 w 的最短路径 P[v][w] 及带权长度 D[v][w] */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) {
    /* 初始化 D 与 P */
    //双重循环初始化
    for (int v = 0; v < G.numVertexes; ++v) {
        for (int w = 0; w < G.numVertexes; ++w) {
            (*D)[v][w] = G.arc[v][w];  /* D[v][w] 值即为对应顶点间的权值 */
            (*P)[v][w] = w;  /* 初始化 P */
        }
    }
    //三重循环更新最短路径
    for (int k = 0; k < G.numVertexes; ++k) {    //k是中间的结点
        for (int v = 0; v < G.numVertexes; ++v) {
            for (int w = 0; w < G.numVertexes; ++w) {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    /* 如果经过下标为 k 的顶点路径比原两点间路径更短 */
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];  /* 将当前两点间权值设为更小的一个 */
                    (*P)[v][w] = (*P)[v][k];  /* 路径设置为经过下标为 k 的顶点 */
                }
            }
        }
    }
}

打印各节点间的最短路径

/* 打印各顶点间的最短路径 */
void ShowShortestPath(MGraph G, Patharc *P, ShortPathTable *D)
{
    for(int v = 0; v < G.numVertexes; ++v)
    {
        for(int w = v + 1; w < G.numVertexes; ++w)
        {
            printf("v%d-v%d weight: %d ",v,w,(*D)[v][w]);
            int k = (*P)[v][w];  /* 获得第一个路径顶点下标 */
            printf(" path: %d",v);  /* 打印源点 */
            while (k != w)  /* 如果路径顶点下标不是终点 */
            {
                printf(" -> %d",k); /* 打印路径顶点 */
                k = (*P)[k][w];  /* 获得下一个路径顶点下标 */
            }
            printf(" -> %d\n",w);   /* 打印终点 */
        }
        printf("\n");
    }
}

 上一篇
1.1 安卓5.0新特性1.1.1 Android 5.0 主要新特性1. 全新的 Material Design 新风格 2. 支持多种设备 3. 全新的通知中心设计 4. 支持 64 位 ART 虚拟机(ART:Android runt
2019-10-26 Xu Canyou
下一篇 
  目录