文章目录
  1. 1. 引入
  2. 2. 最短路径的解决算法
  3. 3. Dijkstra算法
    1. 3.0.0.1. 定义概览
    2. 3.0.0.2. 算法描述
  4. 3.0.1. 代码
  • 4. 例题
    1. 4.1. 路径
      1. 4.1.0.1. 代码
  • 引入

    假设一个开车的人希望找出从新疆到北京的可能的最短路线。他有一张中国公路地图,该公路图上标出了每一对相邻的公路交叉之间的距离,他应该如何找出这一最短路线呢?

    一种可能的方法就是枚举出所有从新疆到北京之间的路线,依然存在着数以百万计的行车路线,而其中绝大多数是不值得考虑的。

    现实中很多抽象的例子都可以转化成类似这样的问题,这类问题统一称为求最短路径的问题。

    最短路径的解决算法

    • Floyd
      求多源、无负权边的最短路。用矩阵记录图。时效性较差,时间复杂度O(V^3)
    • Dijkstra
      求单源、无负权的最短路。时效性较好,时间复杂度O(V^2)
    • Bellman-Ford
      求单源最短路,可以判断有无负权回路。通过不断构建以源点为根的最短路径树,不断扩展。
    • SPFA
      可以用于存在负数边权的图,算法时间效率是不稳定的,即它对于不同的图所需要的时间有很大的差别。SPFA算法是在Bellman-Ford算法的基础上进行优化而来。

    Dijkstra算法

    定义概览

    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。

    算法描述

    算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点vS中各顶点的最短路径长度不大于从源点vU中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

    算法步骤

    1. 初始时,S只包含源点,即S={v}v的距离为0U包含除v外的其他顶点,即:U={其余顶点},若vU中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为

    2. 从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是vk的最短路径长度)。

    3. k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值为顶点k的距离加上<k,u>边上的权。

    4. 重复步骤 23 直到所有顶点都包含在 S 中。

    Tip:
    通常在编码过程中,以一个二维数组map[][]来表示整张图,以一个一维数组dist[]来表示源点到各个顶点的当前最短路径,以一个一维数组set[]来标识当前顶点是否已经被并入到集合S中,即当前顶点的最短路径已经求出。

    执行动画:

    dijkstra_img

    代码

    由上述讲解可以写出如下Dijkstra算法代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    // 图的存储在 MGraph  g.n为顶点数量 g.edges[][]为边的权值
    // v为源点
    // dist[] 保存源点到各个顶点的当前最短路径
    void Dijkstra(MGraph g, int v, int dist[]) {
    int set[maxSize];
    int min,i,j,u;
    // 初始化
    for(i = 0;i<g.n;i++) {
    dist[i] = g.edges[v][i];
    set[i] = 0;
    }
    set[v] = 1;

    for(i = 0;i < g.n; i++ ) {
    min = INF;
    // 这个循环每次从剩余顶点中选出一个顶点,通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的
    for (j = 0;j< g.n;j++) {
    if(set[h] == 0 && dist[j] < min) {
    u = j;
    min = dist[j];
    }
    }
    set[u] = 1;
    // 以刚并入的顶点作为中间点,对所有通往剩余顶点的路径进行检测
    for (j = 0;j < g.n;j++) {
    if (set[j]==0&&dist[u]+g.edges[u][j]<dist[j]) {
    dist[j] = dist[u]+g.edges[u][j];
    }
    }
    }

    }

    例题

    例如经典的题目HDU1874

    问题描述

    某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
    现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。

    Input:

    本题目包含多组数据,请处理到文件结束。
    每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N-1编号。
    接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
    再接下一行有两个整数S,T(0<=S,T<N),分别代表起点和终点。

    Output:

    对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.

    解析

    这是典型的求解最短路径的问题,可以把城镇转换成图中的点,道路转换成图中的有权边,然后根据构造出的这张图,求解源点到各个点的最短路径即可。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    #include "stdio.h"
    #define MAX_INT 10000
    //
    int set[202];
    int map[202][202];
    int dis[202];


    void Dijkstra(int start , int n) {

    // 初始化
    for (int i = 0; i<n; i ++) {
    dis[i] = map[start][i];
    set[i] = 0;
    }
    set[start] = 1;

    for (int j = 0 ; j < n; j ++) {

    // 找当前最短路径
    int temp = MAX_INT;
    int u = start;
    for (int i = 0; i < n; i ++) {
    if (set[i] == 0 && dis[i] < temp) {
    temp = dis[i];
    u = i;
    }
    }
    set[u] = 1;

    // 以u为中间点更新最短路径
    for (int i = 0 ; i < n; i ++) {
    if (set[i] == 0 && dis[u] + map[u][i] < dis[i]) {
    dis[i] = dis[u] + map[u][i];
    }
    }
    }

    }

    int main(int argc, const char * argv[]) {
    int n,m;
    int a,b,c;
    while (scanf("%d %d",&n,&m) != EOF) {
    // 图的初始化
    for (int i = 0; i < n; i ++) {
    for (int j = 0; j < n; j ++) {
    if (i == j) {
    map[i][j] = 0;
    } else {
    map[i][j] = MAX_INT;
    }
    }
    }
    while (m--) {
    scanf("%d%d%d",&a,&b,&c);
    if (c < map[a][b]) {
    map[a][b] = map[b][a] = c;
    }
    }
    int start , end;
    scanf("%d%d",&start,&end);
    Dijkstra(start, n);
    if (dis[end] == MAX_INT) {
    printf("-1\n");
    } else {
    printf("%d\n",dis[end]);
    }
    }
    return 0;
    }

    几个变形题目,可以当做练习:

    练习题

    password:123

    路径

    经过以上步骤,我们已经求出了源点到各个顶点的最短路径的值,如果此时需要知道该最短路径所上所经过的点,该如何解决呢?

    此时我们可以用一个一维数组path[]来保存最短路径上所经过的订单。
    比如:path[Vi]中保存从源点到Vi的最短路径上Vi的前一个顶点,假设最短路径上的顶点序列为V0,V1,V2,V3,...,Vi-1,Vipath[Vi]=Vi-1

    path[]测初态为:假设V0为源点,如果V0Vi有边,则path[Vi]=V0,否则path[Vi]=-1
    在上面的步骤中,每一次更新最短路径的值的时候,同时更新path[]的值,直到所有的顶点的最短路径更新完毕,path[]中也就保存了每个最短路径所经历的顶点,这是一个树形结构

    代码

    在上面的代码上做一些修改,增加了path[]数组:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    // 图的存储在 MGraph  g.n为顶点数量 g.edges[][]为边的权值
    // v为源点
    // dist[] 保存源点到各个顶点的当前最短路径
    // path[] 保存从源点到`Vi`的最短路径上`Vi`的前一个顶点
    void Dijkstra(MGraph g, int v, int dist[], int path[]) {
    int set[maxSize];
    int min,i,j,u;
    // 初始化
    for(i = 0;i<g.n;i++) {
    dist[i] = g.edges[v][i];
    set[i] = 0;
    // path[] 初始化
    if (g.edges[v][i] < INF) {
    path[i] = v;
    } else {
    path[i] = -1;
    }
    }
    set[v] = 1;
    path[v] = -1;

    for(i = 0;i < g.n; i++ ) {
    min = INF;
    // 这个循环每次从剩余顶点中选出一个顶点,通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的
    for (j = 0;j< g.n;j++) {
    if(set[h] == 0 && dist[j] < min) {
    u = j;
    min = dist[j];
    }
    }
    set[u] = 1;
    // 以刚并入的顶点作为中间点,对所有通往剩余顶点的路径进行检测
    for (j = 0;j < g.n;j++) {
    if (set[j]==0&&dist[u]+g.edges[u][j]<dist[j]) {
    dist[j] = dist[u]+g.edges[u][j];
    path[j] = u;
    }
    }
    }

    }
    文章目录
    1. 1. 引入
    2. 2. 最短路径的解决算法
    3. 3. Dijkstra算法
      1. 3.0.0.1. 定义概览
      2. 3.0.0.2. 算法描述
    4. 3.0.1. 代码
  • 4. 例题
    1. 4.1. 路径
      1. 4.1.0.1. 代码