代码

/*
 * 使用 Bellman-Ford 算法计算指定起点到终点的最短路径及其长度，同时检测图中是否存在负权回路。
 * 
 * 功能：
 * 使用 Bellman-Ford 算法计算指定起点到终点的最短路径，并输出路径和路径长度。
 * 检测图中是否存在负权回路，如果存在则输出相关信息。
 * 用户输入起点和终点的编号，程序输出最短路径及其长度。
 */

#include <iostream>
#include <string>
#include <vector>
#include <climits> // 引入 INT_MAX 用于表示无穷大
using namespace std;

#define Num 13  // 顶点数（游玩项目数）
#define INF INT_MAX  // 定义无穷大，用于表示不可达路径

// 定义边结点结构体（用于表示游乐场项目之间的路线）
typedef struct ArcNode {
    int adjvex;  // 该边所指向的顶点的位置（该路线所指向的游玩项目的编号）
    ArcNode* nextarc;  // 指向下一条边的指针，形成链表结构（用于连接其他边）
    int info;  // 与边相关的信息（如路线长度）
} ArcNode;

// 定义顶点结点结构体（用于表示游乐场中的每个项目）
typedef struct VNode {
    string data;  // 顶点的信息（如游玩项目的名称）
    ArcNode* firstarc;  // 指向顶点相关的第一条边（路线）的指针
} VNode, AdjList[Num];  // 定义一个包含 Num 个顶点的数组，用于表示图的邻接表

// 定义图的结构体
typedef struct {
    AdjList vertices;  // 存放所有顶点的数组（邻接表）
    int vexnum, arcnum;  // 当前图的顶点数和边数
} ALGraph;

// 添加边的函数，用于在图中添加一条边（路线）
void addEdge(ALGraph& G, int start, int end, int weight) {
    ArcNode* newNode = new ArcNode;  // 创建一个新的边结点
    newNode->adjvex = end;  // 设置该边指向的目标顶点编号
    newNode->info = weight;  // 设置边的信息（如路线的长度）
    newNode->nextarc = G.vertices[start].firstarc;  // 将新边的 nextarc 指向当前顶点的第一条边
    G.vertices[start].firstarc = newNode;  // 更新当前顶点的第一条边为新添加的边
}

// Bellman-Ford 算法，用于计算从起点到其他所有节点的最短路径
bool BellmanFord(ALGraph& G, int start, vector<int>& dist, vector<int>& pred) {
    dist.assign(G.vexnum, INF);  // 初始化所有节点的最短路径为无穷大
    pred.assign(G.vexnum, -1);  // 初始化前驱节点数组
    dist[start] = 0;  // 起点到起点的距离为0

    // 进行 V-1 次松弛操作
    for (int i = 1; i < G.vexnum; ++i) {
        for (int u = 0; u < G.vexnum; ++u) {  // 遍历所有顶点
            ArcNode* p = G.vertices[u].firstarc;  // 获取顶点 u 的第一条边
            while (p != nullptr) {  // 遍历与 u 相邻的所有边
                int v = p->adjvex;  // 获取边的目标节点
                int weight = p->info;  // 获取边的权重（长度）
                // 如果从 u 到 v 的距离比当前记录的最短距离更短
                if (dist[u] != INF && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;  // 更新 v 的最短距离
                    pred[v] = u;  // 记录前驱节点
                }
                p = p->nextarc;  // 移动到下一条边
            }
        }
    }

    // 检测负权回路
    for (int u = 0; u < G.vexnum; ++u) {  // 遍历所有顶点
        ArcNode* p = G.vertices[u].firstarc;  // 获取顶点 u 的第一条边
        while (p != nullptr) {  // 遍历与 u 相邻的所有边
            int v = p->adjvex;  // 获取边的目标节点
            int weight = p->info;  // 获取边的权重（长度）
            // 如果可以进一步松弛，说明存在负权回路
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                cout << "图中存在负权回路。" << endl;
                return false;  // 返回 false 表示存在负权回路
            }
            p = p->nextarc;  // 移动到下一条边
        }
    }

    return true;  // 返回 true 表示没有负权回路
}

// 打印路径
void printPath(vector<int>& pred, int end) {
    if (pred[end] == -1) {  // 如果没有前驱节点，表示起点
        cout << end + 1;  // 输出节点编号
        return;
    }
    printPath(pred, pred[end]);  // 递归打印前驱节点
    cout << " -> " << end + 1;  // 输出当前节点编号
}

int main() {
    ALGraph G;  // 创建图的实例
    G.vexnum = Num;  // 设置图的顶点数量
    G.arcnum = 24;  // 设置图的边数量

    // 初始化顶点名称（游玩项目名称）
    string vertexNames[Num] = { 
        "胡迪牛仔", "创极速光轮", "小飞象", "太空幸会史迪奇", 
        "旋转蜂蜜罐", "爱丽丝迷宫", "旋转木马", "美妙记忆屋", 
        "小矮人矿车", "雷明山漂流", "热力追踪", "加勒比海盗", "飞跃地平线" 
    };

    // 初始化图中的每个顶点
    for (int i = 0; i < Num; i++) {
        G.vertices[i].data = vertexNames[i];  // 设置顶点的名称
        G.vertices[i].firstarc = nullptr;  // 初始化顶点的第一条边为 nullptr
    }

    // 添加边（双向边），根据提供的数据添加边的起点、终点及长度
    addEdge(G, 0, 1, 523); addEdge(G, 1, 0, 523);
    addEdge(G, 1, 3, 153); addEdge(G, 3, 1, 153);
    addEdge(G, 7, 3, 520); addEdge(G, 3, 7, 520);
    addEdge(G, 2, 1, 431); addEdge(G, 1, 2, 431);
    addEdge(G, 0, 2, 367); addEdge(G, 2, 0, 367);
    addEdge(G, 3, 2, 273); addEdge(G, 2, 3, 273);
    addEdge(G, 3, 6, 415); addEdge(G, 6, 3, 415);
    addEdge(G, 7, 6, 161); addEdge(G, 6, 7, 161);
    addEdge(G, 0, 4, 263); addEdge(G, 4, 0, 263);
    addEdge(G, 2, 5, 286); addEdge(G, 5, 2, 286);
    addEdge(G, 6, 2, 211); addEdge(G, 2, 6, 211);
    addEdge(G, 6, 5, 382); addEdge(G, 5, 6, 382);
    addEdge(G, 6, 9, 249); addEdge(G, 9, 6, 249);
    addEdge(G, 5, 4, 157); addEdge(G, 4, 5, 157);
    addEdge(G, 5, 8, 12); addEdge(G, 8, 5, 12);
    addEdge(G, 5, 11, 294); addEdge(G, 11, 5, 294);
    addEdge(G, 6, 11, 358); addEdge(G, 11, 6, 358);
    addEdge(G, 9, 11, 343); addEdge(G, 11, 9, 343);
    addEdge(G, 4, 10, 150); addEdge(G, 10, 4, 150);
    addEdge(G, 4, 8, 144); addEdge(G, 8, 4, 144);
    addEdge(G, 8, 10, 284); addEdge(G, 10, 8, 284);
    addEdge(G, 8, 11, 256); addEdge(G, 11, 8, 256);
    addEdge(G, 11, 12, 361); addEdge(G, 12, 11, 361);
    addEdge(G, 9, 12, 300); addEdge(G, 12, 9, 300);

    int start, end;
    // 获取用户输入的起点和终点
    cout << "请输入起点的代号（1-" << Num << "）：";
    cin >> start;
    cout << "请输入终点的代号（1-" << Num << "）：";
    cin >> end;
    
    start--;  // 将输入的顶点代号转换为索引
    end--;

    // 检查输入的有效性
    if (start < 0 || start >= Num || end < 0 || end >= Num) {
        cout << "输入的顶点代号无效，请重新输入。" << endl;
        return 0;
    }

    vector<int> dist, pred;  // 定义距离和前驱数组
    // 执行 Bellman-Ford 算法
    if (BellmanFord(G, start, dist, pred)) {
        cout << "最短路径为: ";
        printPath(pred, end);  // 打印最短路径
        cout << endl;
        cout << "最短路径长度：" << dist[end] << " 米" << endl;  // 输出最短路径长度
    } else {
        cout << "无法找到最短路径，因为图中存在负权回路。" << endl;
    }

    return 0;
}

评测结果