C++ Bellman-Ford 算法

2024 年 8 月 28 日 | 阅读 19 分钟

在本教程中，我们将学习 C++ 编程语言中 Bellman-Ford 算法的实现。

历史

Bellman-Ford 算法是一种动态规划算法，用于在加权有向图中查找从单个源顶点到所有其他顶点的最短路径。当图可能包含负权重边，并且没有负权重循环时，它特别有用。

以下是 Bellman-Ford 算法的简要历史：

最短路径的早期算法

在图论和计算机科学的早期，就出现了寻找图中最短路径的问题。早期的算法，如 Dijkstra 算法 (1956)，是为了在具有非负边权重的图中找到最短路径而开发的。

Bellman-Ford 算法的发展 (1958)

Bellman-Ford 算法由 Richard Bellman 和 Lester Ford 于 1958 年独立开发。美国数学家 Richard Bellman 因该算法的命名而受到赞誉。

Lester Ford 也是一位美国数学家，对算法的开发和分析做出了贡献。该算法由 Bellman 在《数学表格和其他计算辅助工具》杂志上发表的一篇题为“通过多个点的最短路径”的论文中发表。

Bellman-Ford 算法最初旨在解决在网格中寻找多个点之间最短路径的问题，该问题在运筹学和交通规划中都有应用。

图论应用

Bellman-Ford 算法在开发后不久就被应用于解决图中的单源最短路径问题。人们认识到该算法可以处理具有正负边权重的图。

该算法的关键在于松弛原理，它迭代地改进到顶点的距离估计，直到它们收敛到最短路径。

贡献和进一步发展

计算机科学家和数学家随后的工作主要集中在优化 Bellman-Ford 算法和分析其复杂性。

1959 年，Edward F. Moore 发表了 Bellman-Ford 算法的一个变体，称为 Moore-Bellman-Ford 算法，在某些情况下效率更高。

该算法已在网络路由、计算机网络和交通系统等各个领域得到应用。

复杂性分析和负循环的否定

研究人员还研究了 Bellman-Ford 算法及其变体的计算复杂性。已知其时间复杂性为 O(V * E)，其中 V 是图中的顶点数，E 是边数。

需要注意的是，Bellman-Ford 算法无法处理带有负权重循环的图，因为在这样的图中没有明确定义的最短路径。

Bellman-Ford 算法仍然是解决单源最短路径问题的基本且通用的工具，尤其是在处理可能包含负边权重的图时。它对计算机科学、运筹学和交通规划等各个领域都产生了重大影响。

应用

计算机网络中的路由

Bellman-Ford 算法用于计算机网络中，以查找数据包从一个节点传输到另一个节点的最短路径。当处理具有可变链路成本或可能存在负权重的网络时，它特别有用。

距离向量路由协议

RIP（路由信息协议）等距离向量路由协议使用 Bellman-Ford 算法的变体来确定计算机网络中数据传输的最佳路由。

网络设计与优化

在网络设计中，Bellman-Ford 算法可以帮助确定网络组件的最佳位置，以最小化成本或延迟。

交通与物流

在交通和物流中，Bellman-Ford 算法可用于查找车辆到达目的地的最短路线，同时考虑道路状况和交通等因素。

电信

电信网络通常涉及复杂的路由问题，其中 Bellman-Ford 算法可用于优化信号路由或最小化通信成本。

机器人和自动驾驶汽车

自动驾驶汽车和机器人通常使用 Bellman-Ford 等寻路算法来规划路线，同时避开障碍物并最大限度地缩短行驶时间。

游戏开发

在视频游戏开发中，Bellman-Ford 算法可用于寻路，允许非玩家角色 (NPC) 或游戏角色高效地导航游戏环境。

制造业中的资源分配

在制造业中，该算法可应用于优化机器或人员等资源向不同任务或生产流程的分配。

航空公司航班调度

航空公司使用优化算法，包括 Bellman-Ford 算法的变体，来高效地调度航班和分配资源，同时考虑飞机可用性和机场限制等因素。

项目管理

在项目管理中，该算法可以帮助确定项目网络中的关键路径，该路径表示必须在最短时间内完成以满足项目截止日期的任务序列。

地理信息系统 (GIS)

GIS 应用程序使用 Bellman-Ford 算法执行各种任务，例如在地图上查找位置之间的最短路径、GPS 导航的路线规划以及分析空间数据。

城市规划和交通管理

城市规划者和交通管理系统使用该算法来优化交通流量、减少拥堵并改善交通基础设施。

C++ 中 Bellman-Ford 算法的实现

#include <iostream>
#include <vector>

using namespace std;

// Structure to represent an edge in the graph
struct Edge {
    int source, destination, weight;
};

// Function to find the shortest path using Bellman-Ford algorithm
void bellmanFord(vector<Edge>& edges, int V, int source) {
    vector<int> distance(V, INT_MAX);

    // Initialize distance to the source vertex as 0
    distance[source] = 0;

    // Relax all edges V-1 times
    for (int i = 1; i <= V - 1; ++i) {
        for (const Edge& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;

            if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Check for negative weight cycles
    for (const Edge& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;

        if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
            cout << "Graph contains a negative weight cycle!" << endl;
            return;
        }
    }

    // Print the shortest distances
    cout << "Shortest distances from source vertex " << source << ":" << endl;
    for (int i = 0; i < V; ++i) {
        cout << "Vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int V, E;
    cout << "Enter the number of vertices and edges: ";
    cin >> V >> E;

    vector<Edge> edges;

    cout << "Enter the edges in the format (source, destination, weight):" << endl;
    for (int i = 0; i < E; ++i) {
        int source, destination, weight;
        cin >> source >> destination >> weight;
        edges.push_back({source, destination, weight});
    }

    int source;
    cout << "Enter the source vertex: ";
    cin >> source;

    bellmanFord(edges, V, source);

    return 0;
}

输出

Enter the number of vertices and edges: 5 7
Enter the edges in the format (source, destination, weight):
0 1 2
0 2 4
1 2 -1
1 3 3
2 3 5
3 0 -2
4 3 1
Enter the source vertex: 0
Shortest distances from source vertex 0:
Vertex 0: 0
Vertex 1: 2
Vertex 2: 1
Vertex 3: -1
Vertex 4: 9223372036854775807

说明

1. 初始化

初始化一个距离向量或数组来存储从源顶点到所有其他顶点的暂定距离。将源顶点的距离设置为 0，将所有其他顶点的距离设置为无穷大。

2. 松弛

重复以下步骤 (V - 1) 次，其中 V 是图中的顶点数

对于图中的每条边，检查到源顶点的当前最短距离，如果找到更短的路径则更新它。新距离计算为到源顶点的距离与边权重的总和。如果这个新距离比之前已知的到目的顶点的距离短，则更新距离。

3. 负权重循环检测

执行 (V - 1) 次松弛步骤后，再次遍历所有边，检查是否存在仍然可以松弛的边（即是否存在更短的路径）。如果找到任何此类边，则表明图中存在负权重循环。

4. 最短路径结果

如果在步骤 3 中未检测到负权重循环，则距离向量将包含从源顶点到所有其他顶点的最短距离。您可以使用此信息来查找最短路径本身。

关键点

该算法通过迭代改进距离估计，直到它们收敛到最短路径。
它可以处理具有负权重边的图，但不能处理具有负权重循环的图。
时间复杂度为 O(V * E)，其中 V 是顶点数，E 是边数。

用例

Bellman-Ford 算法用于各种应用，包括计算机网络中的路由、网络设计、交通和物流规划、机器人寻路等。
当可能存在负边权重或由于负权重而无法应用 Dijkstra 算法等其他算法时，它尤其有价值。

示例

示例 1：使用邻接表

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int source, destination, weight;
};

void bellmanFord(vector<Edge>& edges, int V, int source) {
    vector<int> distance(V, INT_MAX);
    distance[source] = 0;

    // Relax edges (V - 1) times
    for (int i = 1; i <= V - 1; ++i) {
        for (const Edge& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;

            if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Check for negative weight cycles
    for (const Edge& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;

        if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
            cout << "Graph contains a negative weight cycle!" << endl;
            return;
        }
    }

    // Print the shortest distances
    cout << "Shortest distances from source vertex " << source << ":" << endl;
    for (int i = 0; i < V; ++i) {
        cout << "Vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int V, E;
    cout << "Enter the number of vertices and edges: ";
    cin >> V >> E;

    vector<Edge> edges;

    cout << "Enter the edges in the format (source, destination, weight):" << endl;
    for (int i = 0; i < E; ++i) {
        int source, destination, weight;
        cin >> source >> destination >> weight;
        edges.push_back({source, destination, weight});
    }

    int source;
    cout << "Enter the source vertex: ";
    cin >> source;

    bellmanFord(edges, V, source);

    return 0;
}

输出

Enter the number of vertices and edges: 5 8
Enter the edges in the format (source, destination, weight):
0 1 2
0 2 4
1 2 -1
1 3 3
2 3 5
3 0 -2
4 3 1
4 2 -3
Enter the source vertex: 0
Shortest distances from source vertex 0:
Vertex 0: 0
Vertex 1: 2
Vertex 2: 1
Vertex 3: -1
Vertex 4: 0

说明

在此示例中，我们使用图的邻接表表示来实现 Bellman-Ford 算法。以下是代码的详细说明：

头文件和命名空间

我们包含必要的 C++ 库用于输入/输出 (iostream) 和数据结构 (vector)。

我们使用 namespace std; 以避免在标准库函数和对象前加上 std::。

边结构

我们定义了一个结构体 Edge 来表示图中的一条边。它包含三个字段：source（边的起始顶点）、destination（边的结束顶点）和 weight（与边相关的权重或成本）。

bellmanFord 函数

这是实现 Bellman-Ford 算法的主函数。

它接受三个参数：

edges： Edge 结构体向量，表示图中的边。

V：图中的顶点数。

source： 查找最短路径的源顶点。

在函数内部，我们初始化一个距离向量来存储从源顶点到所有其他顶点的暂定距离。最初，所有距离都设置为 INT_MAX，除了源顶点，它设置为 0。

松弛循环

该函数在循环中执行边的松弛，该循环运行 (V - 1) 次（其中 V 是顶点数）。此循环迭代地更新到顶点的距离。

它遍历所有边并检查是否存在通过源顶点到目的顶点的更短路径。如果找到更短的路径，则更新距离。

负权重循环检测

在松弛循环之后，代码通过再次遍历所有边来检查是否存在负权重循环。如果在 (V - 1) 次迭代后仍然找到更短的路径，则表明图中存在负权重循环。

打印最短距离

如果未检测到负权重循环，则代码打印从源顶点到所有其他顶点的最短距离。

主函数

在主函数中，系统提示用户输入顶点数、边数和边详细信息。然后，调用 bellmanFord 函数执行最短路径计算。

示例 2：使用邻接矩阵

#include <iostream>
#include <vector>

using namespace std;

void bellmanFord(vector<vector<int>>& graph, int V, int source) {
    vector<int> distance(V, INT_MAX);
    distance[source] = 0;

    // Relax edges (V - 1) times
    for (int i = 1; i <= V - 1; ++i) {
        for (int u = 0; u < V; ++u) {
            for (int v = 0; v < V; ++v) {
                int weight = graph[u][v];
                if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                    distance[v] = distance[u] + weight;
                }
            }
        }
    }

    // Print the shortest distances
    cout << "Shortest distances from source vertex " << source << ":" << endl;
    for (int i = 0; i < V; ++i) {
        cout << "Vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int V, E;
    cout << "Enter the number of vertices and edges: ";
    cin >> V >> E;

    vector<vector<int>> graph(V, vector<int>(V, INT_MAX));

    cout << "Enter the edges in the format (source, destination, weight):" << endl;
    for (int i = 0; i < E; ++i) {
        int source, destination, weight;
        cin >> source >> destination >> weight;
        graph[source][destination] = weight;
    }

    int source;
    cout << "Enter the source vertex: ";
    cin >> source;

    bellmanFord(graph, V, source);

    return 0;
}

输出

Enter the number of vertices and edges: 4 6
Enter the edges in the format (source, destination, weight):
0 1 2
0 2 4
1 2 -1
1 3 3
2 3 5
3 0 -2
Enter the source vertex: 0
Shortest distances from source vertex 0:
Vertex 0: 0
Vertex 1: 2
Vertex 2: 1
Vertex 3: -1

说明

bellmanFord 函数

此函数实现 Bellman-Ford 算法。

它接受三个参数：

graph： 表示图的加权邻接矩阵的二维向量。graph[u][v] 表示从顶点 u 到顶点 v 的边的权重。

V：图中的顶点数。

source： 查找最短路径的源顶点。

距离向量初始化

在函数内部，初始化一个距离向量来存储从源顶点到所有其他顶点的暂定距离。所有距离最初都设置为 INT_MAX，除了到源顶点的距离，它设置为 0。

松弛循环

该函数使用嵌套循环结构执行边的松弛。

它使用两个 for 循环遍历所有顶点对 (u, v)，其中 u 是源顶点，v 是目的顶点。

对于每个顶点对 (u, v)，它检查是否存在从顶点 u 到顶点 v 的更短路径。这是通过比较到 v 的当前距离 (distance[v]) 与到 u 的距离 (distance[u]) 和从 u 到 v 的边的权重 (graph[u][v]) 之和来确定的。

如果找到更短的路径，则 distance[v] 将更新为更短的距离。

打印最短距离

松弛循环完成后，代码打印从源顶点到所有其他顶点的最短距离。

它显示了从源顶点到图中每个顶点的最短距离。

主函数

主函数遵循与示例 1 相似的结构，但输入格式不同。

用户不输入边，而是输入加权邻接矩阵作为二维向量 (graph)。每个条目 graph[u][v] 表示从顶点 u 到顶点 v 的边的权重。

示例 2 展示了当图使用邻接矩阵表示时，如何应用 Bellman-Ford 算法来查找加权图中的最短路径。当图是密集的并且您想使用简单的矩阵结构时，此表示很方便。

示例 3：自定义图表示

在此示例中，我们将使用自定义结构来表示顶点和边。此示例提供了实现 Bellman-Ford 算法的不同视角。

编码

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int source, destination, weight;
};

struct Graph {
    int V, E; // Number of vertices and edges
    vector<Edge> edges;

    Graph(int V, int E) {
        this->V = V;
        this->E = E;
    }

    void addEdge(int source, int destination, int weight) {
        edges.push_back({source, destination, weight});
    }
};

void bellmanFord(Graph& graph, int source) {
    int V = graph.V;
    int E = graph.E;
    vector<int> distance(V, INT_MAX);
    distance[source] = 0;

    // Relax edges (V - 1) times
    for (int i = 1; i <= V - 1; ++i) {
        for (const Edge& edge : graph.edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;

            if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Print the shortest distances
    cout << "Shortest distances from source vertex " << source << ":" << endl;
    for (int i = 0; i < V; ++i) {
        cout << "Vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int V, E;
    cout << "Enter the number of vertices and edges: ";
    cin >> V >> E;

    Graph graph(V, E);

    cout << "Enter the edges in the format (source, destination, weight):" << endl;
    for (int i = 0; i < E; ++i) {
        int source, destination, weight;
        cin >> source >> destination >> weight;
        graph.addEdge(source, destination, weight);
    }

    int source;
    cout << "Enter the source vertex: ";
    cin >> source;

    bellmanFord(graph, source);

    return 0;
}

输出

Enter the number of vertices and edges: 4 6
Enter the edges in the format (source, destination, weight):
0 1 2
0 2 4
1 2 -1
1 3 3
2 3 5
3 0 -2
Enter the source vertex: 0
Shortest distances from source vertex 0:
Vertex 0: 0
Vertex 1: 2
Vertex 2: 1
Vertex 3: -1

说明

头文件和命名空间

代码首先包含必要的 C++ 库，用于输入/输出 (iostream) 和使用向量 (vector)。

using namespace std; 语句用于避免在标准库函数和对象前加上 std::。

边结构

定义了一个名为 Edge 的结构体来表示图中的一条边。

Edge 结构体有三个字段：

source： 边的源顶点。

destination： 边的目的顶点。

weight： 边的权重或成本。

图结构体

定义了另一个名为 Graph 的结构体来表示图。

Graph 结构体有三个字段：

V：图中的顶点数。

E：图中边的数量。

edges： 存储表示图的边的 Edge 对象的向量。

Graph 结构体还包含一个构造函数，用于初始化顶点数 (V) 和边数 (E)。

addEdge 函数

在 Graph 结构体中，有一个 addEdge 函数。

此函数允许您通过指定源顶点、目的顶点和边权重方便地向图中添加边。

它将新边附加到 edges 向量。

bellmanFord 函数

bellmanFord 函数是 Bellman-Ford 算法的主要实现。

它接受两个参数：一个 Graph 对象 (graph) 和查找最短路径的源顶点。

该函数首先初始化一个名为 distance 的向量来存储从源顶点到所有其他顶点的暂定距离。最初，所有距离都设置为 INT_MAX（无穷大），除了到源顶点的距离，它设置为 0。

松弛循环

该函数使用嵌套循环结构来执行边的松弛。

外循环运行 (V - 1) 次迭代，其中 V 是图中的顶点数。

内循环遍历 edges 向量中的所有边，并检查是否存在通过当前权重为 w 的边从源顶点 (u) 到目的顶点 (v) 的更短路径。

如果找到更短的路径，则更新目的顶点的距离。

打印最短距离

松弛循环完成后，代码打印从源顶点到所有其他顶点的最短距离。

它显示了从源顶点到图中每个顶点的最短距离。

主函数

主函数是程序的入口点。

它首先提示用户输入图中顶点数和边数。

它创建一个具有指定顶点数和边数的 Graph 对象 graph。

然后，系统提示用户使用循环输入格式为（源、目的、权重）的边。

最后，要求用户输入查找最短路径的源顶点，并以 graph 和 source 作为参数调用 bellmanFord 函数。

优点

Bellman-Ford 算法具有多项优点，使其成为解决某些类型最短路径问题的宝贵工具：

处理负权重边： Bellman-Ford 算法的主要优点之一是它能够处理具有负权重边的图。这是它与其他一些最短路径算法（如 Dijkstra 算法，不能处理负边权重）不同之处。
适用于分布式系统： 该算法适用于分布式和去中心化系统。它通常用于计算机网络和电信的路由协议中。
无需非负权重： 与假设非负边权重的 Dijkstra 算法不同，Bellman-Ford 算法可在边权重可能为正、负或零时使用。
检测负权重循环： Bellman-Ford 算法可以检测图中是否存在负权重循环。这对于识别由于存在总权重为负的循环而导致不存在最短路径的情况很有用。
应用广泛： 该算法的应用范围超出了传统的寻路。它可以应用于各种优化问题，例如资源分配、项目调度和网络路由。
实现简单： 与 Floyd-Warshall 算法等更复杂的算法相比，Bellman-Ford 算法相对容易实现。它涉及一个简单的迭代过程，即松弛边直到最短距离收敛。
广泛理解： Bellman-Ford 算法是计算机科学和图论中一个成熟且易于理解的算法，因此它对广泛的开发人员和研究人员来说都是可访问的。
确定性输出： 当用于没有负权重循环的图时，Bellman-Ford 算法提供确定性且正确的结果。它保证准确地找到最短路径。
适用于各种图类型： 该算法可应用于不同类型的图，包括有向图和加权图，使其适用于各种场景。

缺点

虽然 Bellman-Ford 算法有其优点，但它也存在某些缺点和局限性，这可能使其不适用于某些场景：

更高的时间复杂度： Bellman-Ford 算法的时间复杂度为 O(V * E)，其中 V 是图中的顶点数，E 是边数。对于大型图，这种时间复杂度可能效率低下，尤其与 Dijkstra 算法等更高效的算法相比，后者具有更好的时间复杂度（邻接矩阵为 O(V^2)，二叉堆为 O((V + E) * log(V))）。
密集图效率低下： 该算法的时间复杂度使其对于边数众多的密集图特别低效，因为它涉及大量迭代。
无短路： Bellman-Ford 算法在找到到所有顶点的最短路径时不会短路。它执行固定次数的迭代，等于顶点数减一，即使最短路径已经确定。这在某些情况下可能导致不必要的计算。
负循环影响正确性： 尽管该算法可以检测负权重循环，但当图中存在此类循环时，它无法提供正确的结果。如果存在负权重循环，该算法可能会产生任意或不正确的最短路径距离。
对于非负权重较慢： 当所有边权重都为非负时，Bellman-Ford 算法的效率低于 Dijkstra 算法。在这种情况下，Dijkstra 算法具有更优越的时间复杂度，是更好的选择。
缺少优先级队列： 与使用优先级队列选择具有最小暂定距离的下一个顶点的 Dijkstra 算法不同，Bellman-Ford 算法在每次迭代中都会探索所有边。这可能会导致对已知已确定最短路径的顶点进行不必要的工作。
有限用例： Bellman-Ford 算法通常在需要考虑负权重或图结构不允许更高效的替代方案时选择。在具有非负权重和性能要求的场景中，通常首选 Dijkstra 算法或 A* 算法等其他算法。
大型图的复杂性： 在大型复杂网络或具有许多顶点和边的图中，Bellman-Ford 算法的时间和空间复杂性可能成为计算资源的限制因素。

结论

Bellman-Ford 算法是图论和网络路由中的一个基本算法。它用于查找从单个源顶点到加权有向图中所有其他顶点的最短路径，即使图中包含负边权重。关于 Bellman-Ford 算法需要记住的关键点包括：

初始化： 该算法使用暂定距离初始化距离向量，该距离设置为无穷大（源顶点除外，它设置为 0）。
松弛： 它迭代地松弛边 (V - 1) 次，其中 V 是顶点数，以改进距离估计并找到最短路径。
负权重循环： 该算法可以在松弛阶段检测图中是否存在负权重循环。
应用： Bellman-Ford 用于各种实际应用，包括网络路由、交通规划、机器人寻路等。
优点： 它可以处理带有负边权重的图，并且可以检测负权重循环。它是一种用于查找最短路径的多功能算法。
缺点： 时间复杂度为 O(V * E)，这使其效率低于其他一些算法，尤其是对于密集图。

图表示（邻接表或邻接矩阵）和数据结构的选择可能因具体的实现要求而异。Bellman-Ford 是解决各种最短路径问题的宝贵工具。

下一个主题C++ 中的冒泡排序算法

C++ Bellman-Ford 算法

历史

应用

C++ 中 Bellman-Ford 算法的实现

关键点

用例

示例

示例 1：使用邻接表

示例 2：使用邻接矩阵

示例 3：自定义图表示

优点

缺点

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Bellman-Ford 算法

历史

应用

C++ 中 Bellman-Ford 算法的实现

关键点

用例

示例

示例 1：使用邻接表

示例 2：使用邻接矩阵

示例 3：自定义图表示

优点

缺点

结论

相关帖子

C++ 程序实现任意矩阵的 LU 分解

fgets()/gets()/scanf() 之后 scanf() 的问题

声明返回指向整型指针数组的指针的 C/C++ 函数

在 C++ 中以线性时间找到长度为 3 的递增子序列

C++ Override 关键字

C++ 展平链表

C++ New 和 Delete 运算符的区别

C++ 程序使用迭代计算数字的阶乘