Module: Ford-Bellman algorithm


Problem

1/6

Ford-Bellman: The Beginning (C++)

Theory Click to read/hide

Ford-Bellman algorithm
Let's be given a directed weighted graph G with n vertices and m edges, and some starting vertex v . It is required to find the lengths of the shortest paths from the vertex v to all other vertices.

Like Dijkstra, Ford-Bellman looks for the distance from vertex 1 to all others, but works with negative edges< /strong>.
 
The Ford-Bellman algorithm itself consists of several phases (n-1). At each phase, all the edges of the graph are examined, and the algorithm tries to relax along each edge (a, b) of the cost c. Relaxation along an edge — this is an attempt to improve the meaning of d[a]  the value d[b] + c. In fact, this means that we are trying to improve the answer for the vertex by using the edge  and the current answer for the top.

The d array is an array of the shortest lengths from the starting vertex, just like in Dijkstra, we initially fill it with as large numbers as possible, except for the starting vertex, in which you need to put 0.
To store edges, not an adjacency matrix or a weight matrix is ​​used, but a list that indicates from which node the edge leaves (from), to which it comes (to) and its weight (cost).
  struct edge { int from, to, cost; }; vector<edge> edges;
The INF constant denotes the number "infinity" - it must be chosen in such a way that it obviously exceeds all possible path lengths.

The simplest implementation of the algorithm: d[v] = 0; for (int i=0; i<n-1; ++i) for (int j=0; j<m; ++j)      if (d[edges[j].from] <INF)        d[edges[j].to] = min(d[edges[j].to], d[edges[j].from] + edges[j].cost);

or a little shorter using the syntax C++11:
  d[v] = 0; for (int i=0; i< n-1; ++i) for (edge ​​j: edges) if (d[j.from] <INF) d[j.to] = min(d[j.to], d[j.from] + j.cost);

Work example


Take a simple directed graph  with 5 nodes, 4 edges with weight equal to 1.

Let's introduce a list of edges in that order.
4 5 1
3 4 1
2 3 1
1 2 1

Initial values ​​in array of shortest lengths:
 
0 inf inf inf inf

where inf should be a matched integer that is always greater than the weight of the edge.

After 1st pass
 
0 1 inf inf inf

After the 2nd pass
 
0 1 2 inf inf

After the 3rd pass
 
0 1 2 3 inf


After the 4th pass
 
0 1 2 3 4

If we fed edges in order from 1 to last, we could find the shortest lengths after the 1st pass.

 

Problem

Complete the program so that it correctly solves the following problem.

Given a directed graph that can have multiple edges and loops. Each edge has a weight expressed as an integer (possibly negative). It is guaranteed that there are no negative weight cycles.
You need to calculate the lengths of the shortest paths from vertex number 1 to all other vertices.
 
Input
The program first receives the number N (1 <= N <= 100) – the number of graph vertices and the number M (0 <= M <= 10000) – number of ribs. The following lines contain M of triples of numbers describing the edges: the beginning of the edge, the end of the edge, and the weight (weight – is an integer from -100 to 100).
 
Output
The program should output N numbers – distances from vertex number 1 to all vertices of the graph. If there is no path to the corresponding vertex, print the number 30000 instead of the length of the path.
 
Examples
# Input Output
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 

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++
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!