Module: 福特-贝尔曼算法


Problem

1/6

Ford-Bellman：起点 (C++)

Theory Click to read/hide

福特-贝尔曼算法
让我们得到一个有向加权图 G，它有 n 个顶点和 m 个边，以及一些起始顶点 v 。需要找到从顶点 v 到所有其他顶点的最短路径的长度。

与 Dijkstra 一样， Ford-Bellman 寻找从顶点 1 到所有其他顶点的距离，但使用负边缘 /强>.
<分区> 
Ford-Bellman 算法本身由几个阶段组成 (n-1)。在每个阶段，都会检查图的所有边，算法会尝试沿着成本 c 的每条边 (a, b) 放松。 沿边缘松弛 ——这是对d[a]意义的改进 值 d[b] + c。事实上，这意味着我们正在尝试通过使用边缘来改进顶点的答案 以及顶部的当前答案。

d数组是距离起始顶点最短长度的数组，就像在Dijkstra中一样，我们一开始用尽可能大的数字填充它，除了起始顶点，你需要在其中放入0.
存储边时，不是使用邻接矩阵或权重矩阵，而是一个列表，表示边从哪个节点离开（from），到达（to） code>) 及其重量 (cost)。
  结构边{ int 从，到，成本； }; 矢量<边>边缘；
INF 常量表示数字“无穷大” - 必须以明显超过所有可能路径长度的方式进行选择。

最简单的算法实现： d[v] = 0; for (int i=0; i

或使用语法 C++11 缩短一点：
  d[v] = 0; for (int i=0; i< n-1; ++i) for (edge j: 边) 如果（d[j.from]

工作实例


拿一个简单的有向图 有 5 个节点，4 条边，权重等于 1。

让我们按顺序介绍一个边列表。
4 5 1
3 4 1
2 3 1
1 2 1

最短长度数组的初始值：
  <正文>
其中 inf 应该是一个匹配的整数，它总是大于边的权重。

第一关后
 
0 信息 信息 信息 信息
<正文>
第二关之后
 
0 1 信息 信息 信息
<正文>
第三关之后
 
0 1 2 信息 信息
<正文>

第四关之后
 
0 1 2 3 信息
<正文>
如果我们按从 1 到最后的顺序馈送边，我们可以在第 1 遍之后找到最短的长度。

 

Problem

完成程序，使其正确解决下列问题。

给定一个有向图，它可以有多个边和环。每条边都有一个表示为整数（可能为负）的权重。保证没有负权重循环。
您需要计算从顶点编号 1 到所有其他顶点的最短路径的长度。
 
输入
程序首先接收到数字N (1 <= N <= 100) –图顶点的数量和数量 M (0 <= M <= 10000) –肋骨数。以下行包含描述边的 M 三元组数字：边的起点、边的终点和权重（权重 – 是从 -100 到 100 的整数）。< /分区>
 
输出
程序应该输出N 个数字 –从顶点编号 1 到图中所有顶点的距离。如果没有到相应顶点的路径，则打印数字 30000 而不是路径长度。
 
例子
0 1 2 3 4
<头> <日># <正文>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
        edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {         
    }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!