IGraph使用实例——贝尔曼-福特算法（求解单源最短路径）

1 概述

本文中求解最短路径使用的方法是igraph中基于贝尔曼-福特算法（Bellman-Ford算法）。Bellman-Ford算法是一种用于在加权图中找到从单个源点到所有其他顶点的最短路径的算法。这个算法可以处理包含负权重边的图，但不能处理有负权重循环的图，因为负权重循环会导致最短路径不存在。

2 运行环境

操作系统：win10 64位

编程语言：C/C++

编译平台：vs2019 x64 debug | release

igraph版本： 0.10.12

3 示例代码

在igraph中igraph_distances_bellman_ford 函数被用来执行Bellman-Ford算法。以下是函数的说明：

igraph_distances_bellman_ford(&g, &res, igraph_vss_all(), igraph_vss_all(), &weights, IGRAPH_OUT);

函数参数说明：

&g 是指向图的指针。
&res 是指向矩阵的指针，该矩阵将存储从每个顶点到其他所有顶点的最短路径长度。
igraph_vss_all() 表示源点和目标点都是图中的所有顶点。
&weights 是指向存储边权重的向量的指针。
IGRAPH_OUT 表示算法将基于图的出边来计算最短路径。

Bellman-Ford算法的工作原理是通过迭代松弛边来逐步更新从源点到其他顶点的最短路径估计。这个过程重复进行，直到没有更多的边可以松弛，或者检测到负权重循环为止。在代码中，对于包含负权重的图，算法将正常执行并给出最短路径；而对于包含负权重循环的图，算法将返回错误代码 IGRAPH_ENEGLOOP。

这段代码是一个C语言程序，它使用了IGraph库来计算图中的最短路径。程序分为三个部分，分别处理了三种不同情况的图：只有正权重的图、含有负权重的图以及含有负权重循环的图。下面是对代码的逐行解释。

// 包含IGraph库的头文件
#include <igraph.h>

int main(void) {
    // 声明一个图变量g
    igraph_t g;
    // 声明一个向量weights，用于存储边的权重
    igraph_vector_t weights;
    // 定义一组权重数据，用于正权重图
    igraph_real_t weights_data_0[] = { 0, 2, 1, 0, 5, 2, 1, 1, 0, 2, 2, 8, 1, 1, 3, 1, 1, 4, 2, 1 };
    // 定义另一组权重数据，用于含有负权重的图
    igraph_real_t weights_data_1[] = { 6, 7, 8, -4, -2, -3, 9, 2, 7 };
    // 定义第三组权重数据，用于含有负权重循环的图
    igraph_real_t weights_data_2[] = { 6, 7, 2, -4, -2, -3, 9, 2, 7 };
    igraph_matrix_t res;

    /* Graph with only positive weights */
    // 创建一个有10个顶点的有向图，添加边和对应的权重，-1表示边的列表结
    igraph_small(&g, 10, IGRAPH_DIRECTED,
                 0, 1, 0, 2, 0, 3,    1, 2, 1, 4, 1, 5,
                 2, 3, 2, 6,         3, 2, 3, 6,
                 4, 5, 4, 7,         5, 6, 5, 8, 5, 9,
                 7, 5, 7, 8,         8, 9,
                 5, 2,
                 2, 1,
                 -1);
    // 创建一个视图，将weights_data_0数组作为weights向量的底层数据
    igraph_vector_view(&weights, weights_data_0,
                       sizeof(weights_data_0) / sizeof(weights_data_0[0]));
    // 计算数组元素个数
    igraph_matrix_init(&res, 0, 0);
    // 计算从所有顶点到所有其他顶点的最短路径（使用Bellman-Ford算法，权重向量为weights，按出边）
    igraph_distances_bellman_ford(&g, &res, igraph_vss_all(), igraph_vss_all(),
                                  &weights, IGRAPH_OUT);
    // 打印矩阵res中的结果
    igraph_matrix_print(&res);
    // 销毁矩阵res
    igraph_matrix_destroy(&res);
    // 销毁图g
    igraph_destroy(&g);

    printf("\n");

    /***************************************/

    /* Graph with negative weights */
    // 创建一个有5个顶点的有向图，并添加边和对应的权重
    igraph_small(&g, 5, IGRAPH_DIRECTED,
                 0, 1, 0, 3, 1, 3, 1, 4, 2, 1, 3, 2, 3, 4, 4, 0, 4, 2, -1);
    // 使用weights_data_1数组作为权重
    igraph_vector_view(&weights, weights_data_1,
                       sizeof(weights_data_1) / sizeof(weights_data_1[0]));
    // 重新初始化矩阵res
    igraph_matrix_init(&res, 0, 0);
    // 计算从所有顶点到所有其他顶点的最短路径
    igraph_distances_bellman_ford(&g, &res, igraph_vss_all(),
                                  igraph_vss_all(), &weights, IGRAPH_OUT);
    // 打印矩阵res中的结果
    igraph_matrix_print(&res);

    /***************************************/

    /* Same graph with negative loop */
    // 设置错误处理函数，忽略错误
    igraph_set_error_handler(igraph_error_handler_ignore);
    // 使用weights_data_2数组作为权重
    igraph_vector_view(&weights, weights_data_2,
                       sizeof(weights_data_2) / sizeof(weights_data_2[0]));
    
    // 尝试计算最短路径,检查是否有负权重循环
    if (igraph_distances_bellman_ford(&g, &res, igraph_vss_all(),
                                      igraph_vss_all(),
                                      &weights, IGRAPH_OUT) != IGRAPH_ENEGLOOP) {
        // 如果没有检测到负权重循环，返回错误代码1
        return 1;
    }
    // 销毁矩阵res
    igraph_matrix_destroy(&res);
    // 销毁图g
    igraph_destroy(&g);

    // 检查是否有未完成的操作
    if (!IGRAPH_FINALLY_STACK_EMPTY) {
        // 如果有，返回错误代码1
        return 1;
    }
    // 正常退出，返回0
    return 0;
}