最短路径算法——数据结构系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

图的最短路径问题是图论中的核心应用问题之一，指的是在带权图中，找到从一个顶点到另一个顶点的路径，使得路径上的边权之和最小。根据图的特性（有向 / 无向、边权正负）和求解需求（单源 / 多源），常用的最短路径算法分为 Dijkstra 算法、Bellman-Ford 算法、Floyd-Warshall 算法三类。本文将详细讲解三类最短路径算法在图结构中的应用，内容由浅入深，所有代码可直接编译运行。

图结构的实现方式：

邻接矩阵图：是一种使用「一维数组 + 二维数组」存储顶点和边数据的图结构，稠密图中常被采用；
邻接链表图：是一种使用「数组 + 链表」存储顶点和边数据的图结构，稀疏图中常被采用；

学习经典应用场景前，请根据上面的教程封装好自定义图，所有场景实例直接复用

教程目录导航

▼

树结构经典应用场景

一、基础概念

1.1 关键概念

在学习算法前，先明确几个关键概念：

带权图：图的每条边都有一个权重值（可以是距离、时间、成本等）。
单源最短路径：从一个固定起点（源点）到其他所有顶点的最短路径。
多源最短路径：求解图中任意两个顶点之间的最短路径。
负权边：边的权重为负数的边；负权环：路径权重之和为负数的环，存在负权环的图没有最短路径（可以绕环无限减小路径权重）。

1.2 算法对比与选择

特性	Dijkstra 算法	Bellman-Ford 算法	Floyd-Warshall 算法
问题类型	单源最短路径	单源最短路径	多源最短路径
负权边支持	❌ 不支持	✅ 支持	✅ 支持
负权回路检测	❌ 不能	✅ 能	✅ 能
时间复杂度	朴素版 O(v²)、优先队列版 O(e log v)	朴素版 O(ve)、SPFA O(e)最坏 O(ve)	O(V³)
适用图规模	稠密 / 稀疏图	小规模图	小规模图（n≤200）
核心思想	贪心	松弛（动态规划）	动态规划

一、Floyd-Warshall(弗洛伊德)

简称Floyd(弗洛伊德)，是多源最短路径计算算法，可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O(V³)，适用于出现负边权的情况，核心思想是动态规划。

算法原理：

用d[i,j]表示i点到j点的最短距离（为了节约空间直接将最短距离存储在E邻接矩阵中），但i到j可能会经过K个顶点才能找到最短路径,则:
- d[i][j]=d[i][k]+d[k][j],其中的k可能为多个点
遍历全部顶点，如果出现d[i][j]>d[i][k]+d[k][j],我们就用短的距离替换长的距离，用p[i,j]表示i点到j点的最短路径的前驱，即：
- d[i][j]=d[i][k]+d[k][j];
- p[i][j]=p[k][j];

算法解析：

三层循环，第一层循环中间点k，第二，第三层循环起点终点i、j，如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。

初始化距离矩阵和前驱矩阵
- 将自身至自身的距离设置为0
- 初始化路径前驱为自身，将自身至自身的路径前驱设为自身
- 把不相连的点之间的距离设为无穷大(INF)，把这两点看作相隔很远，如果两者之间有最短路径的话，就会更新成最短路径的长度。
依次遍历取出图中的每个结点作为ij的中间结点去更新ij的最短路径
- 如果ik是相连的，ik是相连的
- 并且ik+kj的距离（经过k点）小于ij(不经过k点)的距离
- 更新为ik+kj的距离和前驱
打印任意两点之间的最短路径
- 从终点j反向找前驱，直到起点i
- 逆序输出路径


#include <iostream>
#include <vector>
#include"ArrayGraph.h"

using namespace std;

//Floyd算法计算最短距离和最短前驱
void floydWarshall(ArrayGraph& vGraph, vector>& vPath)
{
    // 1. 初始化距离矩阵和前驱矩阵
    int n = vGraph.vertexNum;

    vPath.resize(n);
    for(int i = 0; i < n; ++i)
    {
        vPath[i].resize(n, NO_EDGE);
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == j) {
                //将自身至自身的距离设置为0
                vGraph.graph[i][j] = 0;
                // 将自身至自身的路径前驱设为自身
                vPath[i][j] = i;
            }
            else if(vGraph.graph[i][j] != NO_EDGE) {
                vPath[i][j] = i;//初始化路径前驱为自身
            } 
            else {
                vGraph.graph[i][j] = INF;//把不相连的点之间的距离设为无穷大(INF)
            }
        }
    }

    // 2. 依次遍历取出图中的每个结点作为ij的中间结点去更新ij的最短路径
    for(int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)// k作为中间结点更新ij最短路径
        {
            for (int j = 0; j < n; j++)
            {
                // 如果ik是相连的 && ki是相连的 && ik+kj的距离（经过k点）小于ij(不经过k点)的距离，就更新为ik+kj的距离和前驱
                if(vGraph.graph[i][k] != INF&& vGraph.graph[k][j] != INF && vGraph.graph[i][k] + vGraph.graph[k][j] < vGraph.graph[i][j])
                {
                    vGraph.graph[i][j] = vGraph.graph[i][k] + vGraph.graph[k][j];// 更新距离
                    vPath[i][j] = vPath[k][j];// 更新前驱
                }
            }
        }
    }
}

// 打印距离和前驱矩阵
void printMatrix(ArrayGraph& vGraph, const vector>& vPath) {
    // 打印距离矩阵
    printf("\n======= 距离矩阵 =======\n");
    // 打印顶点名称（表头）
    printf("   "); // 对齐
    for(int i = 0; i < vGraph.vertexNum; i++) {
        printf("%3c", vGraph.vertices[i]);
    }
    printf("\n");
    for(int i = 0; i < vGraph.vertexNum; ++i)
    {
        printf("%3c",vGraph.vertices[i]);
        for(int j=0;j < vGraph.vertexNum;++j)
        {
            if(vGraph.graph[i][j]==INF)
                printf("%3c",'*');
            else
                printf("%3d",vGraph.graph[i][j]);
        }
        printf("\n");
    }
    printf("========================\n");

    // 打印前驱矩阵
    printf("\n======= 前驱矩阵 =======\n");
    // 打印顶点名称（表头）
    printf("   "); // 对齐
    for(int i = 0; i < vGraph.vertexNum; i++) {
        printf("%3c", vGraph.vertices[i]);
    }
    printf("\n");
    for(int i = 0; i < vGraph.vertexNum; ++i)
    {
        printf("%3c",vGraph.vertices[i]);
        for(int j=0;j < vGraph.vertexNum;++j)
        {
            if(vGraph.graph[i][j]==INF)
                printf("%3c",'*');
            else
                printf("%3d",vPath[i][j]);
        }
        printf("\n");
    }
    printf("========================\n");
}

// 打印任意两点之间的最短路径
void printPath(int i, int j, ArrayGraph& graph, const vector<vector<int>>& vPath) {
    vector<int> path;
    // 1. 从终点j反向找前驱，直到起点i
    for (int cur = j; cur != i; cur = vPath[i][cur]) {
        path.push_back(cur);
    }
    path.push_back(i);

    // 2. 逆序输出路径
    cout << endl;
    cout << "从" << graph.vertices[i] << "到" << graph.vertices[j] << "的路径：";
    for (auto it = path.rbegin(); it != path.rend(); ++it) {
        cout << graph.vertices[*it];
        if (it != path.rend() - 1) cout << " -> ";
    }
    cout << endl;
}


// 测试案例
int main() {
    ArrayGraph graph;
    vector<vector<int>> path;//前驱矩阵

    // 1. 添加顶点（A、B、C、D、E、F、G）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');
    graph.addVertex('G');

    // 2. 添加边（有权无向图）
    graph.addDirectedEdge('A','B',3);
    graph.addDirectedEdge('A','C',1);
    graph.addDirectedEdge('A','D',2);

    graph.addDirectedEdge('B','A',3);
    graph.addDirectedEdge('B','D',2);

    graph.addDirectedEdge('C','A',1);
    graph.addDirectedEdge('C','D',2);
    graph.addDirectedEdge('C','F',2);

    graph.addDirectedEdge('D','A',2);
    graph.addDirectedEdge('D','B',2);
    graph.addDirectedEdge('D','C',2);
    graph.addDirectedEdge('D','E',2);

    graph.addDirectedEdge('E','D',2);
    graph.addDirectedEdge('E','F',4);

    graph.addDirectedEdge('F','C',2);
    graph.addDirectedEdge('F','E',4);
    graph.addDirectedEdge('F','G',3);

    graph.addDirectedEdge('G','F',3);

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. Floyd算法计算最短距离和最短前驱
    floydWarshall(graph, path);

    // 5.打印距离和路径矩阵
    printMatrix(graph, path);

    // 6. 打印任意两点之间的最短路径
    char start='A';
    char target='E';
    int startIndex = graph.findVertexIndex(start);
    int targetIndex = graph.findVertexIndex(target);
    printPath(startIndex,targetIndex,graph, path);
    printf("\n最短路径长度：%d\n", graph.graph[startIndex][targetIndex]);

    return 0;
}

输出结果


 ===== 带权邻接矩阵 =====
     A  B  C  D  E  F  G
  A  0  3  1  2  0  0  0
  B  3  0  0  2  0  0  0
  C  1  0  0  2  0  2  0
  D  2  2  2  0  2  0  0
  E  0  0  0  2  0  4  0
  F  0  0  2  0  4  0  3
  G  0  0  0  0  0  3  0
========================

======= 距离矩阵 =======
     A  B  C  D  E  F  G
  A  0  3  1  2  4  3  6
  B  3  0  4  2  4  6  9
  C  1  4  0  2  4  2  5
  D  2  2  2  0  2  4  7
  E  4  4  4  2  0  4  7
  F  3  6  2  4  4  0  3
  G  6  9  5  7  7  3  0
========================

======= 前驱矩阵 =======
     A  B  C  D  E  F  G
  A  0  0  0  0  3  2  5
  B  1  1  0  1  3  2  5
  C  2  0  2  2  3  2  5
  D  3  3  3  3  3  2  5
  E  3  3  3  4  4  4  5
  F  2  0  5  2  5  5  5
  G  2  0  5  2  5  6  6
========================

从A到E的路径：A -> D -> E
最短路径长度：4

三、Dijkstra

Dijkstra(迪杰斯特拉)，是求单源最短路径的算法，可以计算从一个源节点出发，到其他所有节点的最短路径。Dijkstra的时间复杂度是O(E log V)，Dijkstra算法存在的问题是不支持图中带负权路径。核心思想是贪心策略。

算法原理：

针对一个带权图G，将所有结点分为两组S和Q
1. S是已经确定最短路径的结点集合
2. Q是未确定最短路径的结点集合
每次从Q中找出一个从起点到该结点代价最小的结点u ，将u从Q中移出，并放入S中，对u的每一个相邻结点v（且v不在S中）进行松弛操作。
1. 松弛即对每一个相邻结点v ，判断源节点s到结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小
2. 若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和，否则维持原样
3. 如此一直循环直至集合Q 为空，即所有节点都已经查找过一遍并确定了最短路径

算法解析：

初始化dist距离、pre前驱和sq数组
- 初始化sq默认为false，false代表未确定最短路径的结点集合Q，true代表已经确定最短路径的结点集合S
- 初始化起始顶点到自身距离为0，自身无前驱(NO_PRE)
- 初始化起始顶点的直连边的dist距离为权值，直连边的pre前驱为起始顶点
- 初始化其它顶点的dist距离为无穷大(INF)，pre前驱为无前驱(NO_PRE)
依次计算每个节点的距离和前驱
- 从Q中找出一个从起点到该结点代价最小的结点u
- 将u从Q中移出，并放入S中
- 对u的每一个相邻结点v进行松驰操作
打印最短路径
- 从终点递归回溯前驱数组
- 直到起点或无路径


#include <iostream>
#include"ArrayGraph.h"

using namespace std;

// 打印dist距离、pre前驱和sq数组
void printArray(ArrayGraph& vGraph, int dist[], int pre[], bool sq[]) {
    printf("===========================\n");
    printf("距离：");
    for(int d=0;d < vGraph.vertexNum;d++)
    {
        if(dist[d]==INF) printf("%3c",'*'); else printf("%3d",dist[d]);
    }
    printf("\n");
    printf("前驱：");
    for(int d=0;d < vGraph.vertexNum;d++)
    {
        printf("%3d",pre[d]);
    }
    printf("\n");
    printf("S  Q：");
    for(int d=0;d < vGraph.vertexNum;d++)
    {
        printf("%3d",sq[d]);
    }
    printf("\n");
    printf("===========================\n");
}

// 打印最短路径
void printDijkstraPath(ArrayGraph& graph, int pre[], int startIndex, int targetIndex) {
    if (targetIndex == startIndex) {
        printf("%c", graph.vertices[targetIndex]);
        return;
    }
    if (pre[targetIndex] == NO_PRE) {
        printf("无路径");
        return;
    }
    // 递归打印前驱路径
    printDijkstraPath( graph, pre, startIndex, pre[targetIndex]);
    printf(" -> %c", graph.vertices[targetIndex]);
}

//Dijkstra算法：计算起始顶点到所有顶点的最短路径 startIndex 起始顶点索引  dist 输出参数：存储起始顶点到各顶点的最短距离  pre 输出参数：存储各顶点的路径前驱索引
void dijkstra(ArrayGraph& vGraph, int startIndex, int dist[], int pre[], bool sq[]) {
    int n = vGraph.vertexNum;
    memset(sq, false, MAX_VERTEX);//初始化sq默认为false，false代表未确定最短路径的结点集合Q，true代表已经确定最短路径的结点集合S

    // 1. 初始化距离和前驱数组
    for (int i = 0; i < n; i++) {
        if (i == startIndex) {
            dist[i] = 0;                // 起始顶点到自身距离为0
            pre[i] = NO_PRE;            // 自身无前驱
        } else if (vGraph.graph[startIndex][i] != NO_EDGE) {
            dist[i] = vGraph.graph[startIndex][i];  // 初始化起始顶点的直连边的dist距离为权值
            pre[i] = startIndex;             // 初始化起始顶点的直连边的pre前驱为起始顶点
        } else {
            dist[i] = INF;              // 初始化其它顶点的dist距离为无穷大(INF)
            pre[i] = NO_PRE;            // 初始化其它顶点的pre前驱为无前驱(NO_PRE)
        }
    }
    sq[startIndex] = true;


    // 2. 依次计算每个节点的距离和前驱
    for (int i = 1; i < n; i++) {
        // 从Q中找出一个从起点到该结点代价最小的结点u
        int u = 0;
        int min = INF;
        for (int i = 0; i < n; i++) {
            if (!sq[i] && dist[i] < min) {
                min = dist[i];
                u = i;
            }
        }
        if (u == -1) break; // 所有可达顶点已处理
        sq[u] = true;// 将u从Q中移出，并放入S中

        // 对u的每一个相邻结点v进行松驰操作
        for (int v = 0; v < n; v++) {
            if (!sq[v] && vGraph.graph[u][v] != NO_EDGE && dist[u] != INF) {
                if (dist[u] + vGraph.graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + vGraph.graph[u][v];//更新距离
                    pre[v] = u; // 更新前驱
                }
            }
        }
    }
}

// 测试案例
int main() {
    int dist[MAX_VERTEX];
    int pre[MAX_VERTEX];
    bool sq[MAX_VERTEX];
    ArrayGraph graph;

    // 1. 添加顶点（A、B、C、D、E、F、G）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');
    graph.addVertex('G');

    // 2. 添加边（有权无向图）
    graph.addDirectedEdge('A','B',3);
    graph.addDirectedEdge('A','C',1);
    graph.addDirectedEdge('A','D',2);

    graph.addDirectedEdge('B','A',3);
    graph.addDirectedEdge('B','D',2);

    graph.addDirectedEdge('C','A',1);
    graph.addDirectedEdge('C','D',2);
    graph.addDirectedEdge('C','F',2);

    graph.addDirectedEdge('D','A',2);
    graph.addDirectedEdge('D','B',2);
    graph.addDirectedEdge('D','C',2);
    graph.addDirectedEdge('D','E',2);

    graph.addDirectedEdge('E','D',2);
    graph.addDirectedEdge('E','F',4);

    graph.addDirectedEdge('F','C',2);
    graph.addDirectedEdge('F','E',4);
    graph.addDirectedEdge('F','G',3);

    graph.addDirectedEdge('G','F',3);

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 定义起点和终点
    char start='A';
    char target='F';
    int startIndex = graph.findVertexIndex(start);
    int targetIndex = graph.findVertexIndex(target);

    // 5. 计算距离和前驱
    dijkstra(graph,startIndex,dist,pre,sq);

    // 6. 打印距离和前驱
    printArray(graph, dist, pre,sq);

    // 7. 打印路径（同一顶点，路径长度为0）
    if (startIndex == targetIndex) {
        printf("\n===== 最短路径（%c → %c）=====\n", start, target);
        printf("路径：%c\n", start);
        printf("最短路径长度：0\n");
    }

    // 7. 打印路径
    printf("\n===== 最短路径（%c → %c）=====\n", start, target);
    if (dist[targetIndex] == INF) {
        printf("路径：无\n");
        printf("最短路径长度：∞（无连通路径）\n");
    } else {
        printf("路径：");
        printDijkstraPath(graph, pre, startIndex, targetIndex);
        printf("\n最短路径长度：%d\n", dist[targetIndex]);
    }

    return 0;
}

输出结果


====== 带权邻接矩阵 ======
     A  B  C  D  E  F  G
  A  0  3  1  2  0  0  0
  B  3  0  0  2  0  0  0
  C  1  0  0  2  0  2  0
  D  2  2  2  0  2  0  0
  E  0  0  0  2  0  4  0
  F  0  0  2  0  4  0  3
  G  0  0  0  0  0  3  0
========================
===========================
距离：  0  3  1  2  4  3  6
前驱： -1  0  0  0  3  2  5
S  Q：  1  1  1  1  1  1  1
===========================

===== 最短路径（A → E）=====
路径：A -> D -> E
最短路径长度：4

四、Bellman-Ford

Bellman-Ford（贝尔曼-福特）算法可以解决负权图的单源最短路径问题，如果图中存在负权回路（负权环）的情况，这种情况是求不出最短路径的。

时间复杂度 O(N*E) (N是顶点数，E是边数)普遍是要高于Dijkstra(迪杰斯特拉)算法。如果我们使用邻接矩阵实现，那么时间复杂度就是O(N^3)，因为邻接矩阵的话遍历所有的边就需要O(N^2)。

算法原理：

Bellman-Ford（贝尔曼-福特）算法与Dijkstra(迪杰斯特拉)算法类似：
都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。
只不过Dijkstra(迪杰斯特拉)算法每次去选到起点最短的边，然后去向外扩展更新（即对这条边的终止顶点进行松弛），直至所有的边都更新一遍就可以得到结果（因为它每次选的都是最小的）；
而Bellman-Ford(贝尔曼-福特)算法不管边的大小，就是比较暴力的把所有的边都更新（即先后对所有的顶点的相邻顶点进行松弛），也因此它一遍过后可能得不出最短的路径，可能需要进行多次迭代。

算法解析：

初始化dist距离、pre前驱数组
- 初始化起始顶点到自身距离为0，自身无前驱(NO_PRE)
- 初始化起始顶点的直连边的dist距离为权值，直连边的pre前驱为起始顶点
- 初始化其它顶点的dist距离为无穷大(INF)，pre前驱为无前驱(NO_PRE)
依次计算每个节点的距离和前驱
- 对图中的每一条边进行V-1次遍历，每次遍历都尝试通过当前边来更新终点的最短距离估计。
- 如果通过当前边可以找到一个更短的路径，则更新该终点的距离值和前驱。
打印最短路径
- 从终点递归回溯前驱数组
- 直到起点或无路径


#include <iostream>
#include"ArrayGraph.h"

using namespace std;

// 打印dist距离、pre前驱
void printBellmanArray(ArrayGraph& vGraph, int dist[], int pre[]) {
    printf("===========================\n");
    printf("距离：");
    for(int d=0;d < vGraph.vertexNum;d++)
    {
        if(dist[d]==INF) printf("%3c",'*'); else printf("%3d",dist[d]);
    }
    printf("\n");
    printf("前驱：");
    for(int d=0;d < vGraph.vertexNum;d++)
    {
        printf("%3d",pre[d]);
    }
    printf("\n");
    printf("===========================\n");
}

// 打印最短路径
void printBellmanPath(ArrayGraph& graph, int pre[], int startIndex, int targetIndex) {
    if (targetIndex == startIndex) {
        printf("%c", graph.vertices[targetIndex]);
        return;
    }
    if (pre[targetIndex] == NO_PRE) {
        printf("无路径");
        return;
    }
    // 递归打印前驱路径
    printDijkstraPath( graph, pre, startIndex, pre[targetIndex]);
    printf(" -> %c", graph.vertices[targetIndex]);
}

//Bellman算法：计算起始顶点到所有顶点的最短路径 startIndex 起始顶点索引  dist 输出参数：存储起始顶点到各顶点的最短距离  pre 输出参数：存储各顶点的路径前驱索引
void bellman(ArrayGraph& vGraph, int startIndex, int dist[], int pre[]) {
    int n = vGraph.vertexNum;
    bool flag;

    // 1. 初始化距离和前驱数组
    for (int i = 0; i < n; i++) {
        if (i == startIndex) {
            dist[i] = 0;                // 起始顶点到自身距离为0
            pre[i] = NO_PRE;            // 自身无前驱
        } else if (vGraph.graph[startIndex][i] != NO_EDGE) {
            dist[i] = vGraph.graph[startIndex][i];  // 初始化起始顶点的直连边的dist距离为权值
            pre[i] = startIndex;             // 初始化起始顶点的直连边的pre前驱为起始顶点
        } else {
            dist[i] = INF;              // 初始化其它顶点的dist距离为无穷大(INF)
            pre[i] = NO_PRE;            // 初始化其它顶点的pre前驱为无前驱(NO_PRE)
        }
    }

    // 2. 依次计算每个节点的距离和前驱
    for (int k = 1; k < n; k++) {
        flag = false;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(vGraph.graph[i][j] != NO_EDGE && dist[i] != INF && dist[i]+vGraph.graph[i][j] < dist[j])
                {
                    dist[j] = dist[i]+vGraph.graph[i][j];
                    pre[j] = i;
                    flag = true;
                }
            }
        }

        if(!flag) break;
    }
}


// 测试案例
int main() {
    int dist[MAX_VERTEX];
    int pre[MAX_VERTEX];
    bool sq[MAX_VERTEX];
    ArrayGraph graph;

    // 1. 添加顶点（A、B、C、D、E、F、G）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');
    graph.addVertex('G');

    // 2. 添加边（有权无向图）
    graph.addDirectedEdge('A','B',3);
    graph.addDirectedEdge('A','C',1);
    graph.addDirectedEdge('A','D',2);

    graph.addDirectedEdge('B','A',3);
    graph.addDirectedEdge('B','D',2);

    graph.addDirectedEdge('C','A',1);
    graph.addDirectedEdge('C','D',2);
    graph.addDirectedEdge('C','F',2);

    graph.addDirectedEdge('D','A',2);
    graph.addDirectedEdge('D','B',2);
    graph.addDirectedEdge('D','C',2);
    graph.addDirectedEdge('D','E',2);

    graph.addDirectedEdge('E','D',2);
    graph.addDirectedEdge('E','F',4);

    graph.addDirectedEdge('F','C',2);
    graph.addDirectedEdge('F','E',4);
    graph.addDirectedEdge('F','G',3);

    graph.addDirectedEdge('G','F',3);

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 定义起点和终点
    char start='A';
    char target='G';
    int startIndex = graph.findVertexIndex(start);
    int targetIndex = graph.findVertexIndex(target);

    // 5. 计算距离和前驱
    bellman(graph,startIndex,dist,pre);

    // 6. 打印距离和前驱
    printBellmanArray(graph, dist, pre);

    // 7. 打印路径（同一顶点，路径长度为0）
    if (startIndex == targetIndex) {
        printf("\n===== 最短路径（%c → %c）=====\n", start, target);
        printf("路径：%c\n", start);
        printf("最短路径长度：0\n");
    }

    // 7. 打印路径
    printf("\n===== 最短路径（%c → %c）=====\n", start, target);
    if (dist[targetIndex] == INF) {
        printf("路径：无\n");
        printf("最短路径长度：∞（无连通路径）\n");
    } else {
        printf("路径：");
        printBellmanPath(graph, pre, startIndex, targetIndex);
        printf("\n最短路径长度：%d\n", dist[targetIndex]);
    }

    return 0;
}

输出结果


===== 带权邻接矩阵 =====
     A  B  C  D  E  F  G
  A  0  3  1  2  0  0  0
  B  3  0  0  2  0  0  0
  C  1  0  0  2  0  2  0
  D  2  2  2  0  2  0  0
  E  0  0  0  2  0  4  0
  F  0  0  2  0  4  0  3
  G  0  0  0  0  0  3  0
========================
===========================
距离：  0  3  1  2  4  3  6
前驱： -1  0  0  0  3  2  5
===========================

===== 最短路径（A → G）=====
路径：A -> C -> F -> G
最短路径长度：6

返回顶部