Bellman-Ford algorithm

The Bellman-Ford algorithm finds shortest paths from a single source vertex to all of the other vertices. It is slower than Dijkstra’s algorithm, but handles graphs where negative cycles occur, therefore negative weights are acceptable.

Input

v e s
a b c (e times)
...

v – number of vertices
e – number of edges
s – start vertex
a b c – edge between a and b with weight c

Sample input

3 2 1
0 1 10
1 2 20

Output

This algorithm returns shortest distances from city s to all other cities or message Negative cycle.

Complexity

In the following solution there are two nested loops, so the algorithm runs in O(|V| · |E|) time.

Source code

#include <stdio.h>
#include <vector>
#include <climits>
 
using namespace std;
 
struct Vertex
{
    long long minCost;
};
 
struct Edge
{
    int u;
    int v;  
    int cost;
};
 
 
int main()
{
    int v, e, s;
    scanf("%d %d %d", &v, &e, &s);
 
    //VERTICES
    Vertex * vertices = new Vertex[v + 1];
    for (int i = 0; i <= v; i++)
        vertices[i].minCost = LONG_MAX;
 
    //EDGES
    Edge * edges = new Edge[e];
    for (int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].cost);
    }
 
    //BELLMAN-FORD
    vertices[s].minCost = 0;
    long long newCost;
 
    //relax edges
    for (int i = 0; i < v; i++)
    {
        for (int j = 0; j < e; j++)
        {
            if (vertices[edges[j].u].minCost == LONG_MAX)
                continue;
 
            newCost = vertices[edges[j].u].minCost + edges[j].cost;
            if (vertices[edges[j].v].minCost > newCost)
                vertices[edges[j].v].minCost = newCost;
        }
    }
 
    //check for negative cycles
    for (int j = 0; j < e; j++)
    {
        if (vertices[edges[j].u].minCost == LONG_MAX)
            continue;
 
        if (vertices[edges[j].v].minCost > vertices[edges[j].u].minCost + edges[j].cost)
        {
            printf("Negative cycle");
            return 0;
        }
    }
 
    //RESULT
    for (int i = 0; i <= v; i++)
    {
        if (i != s && vertices[i].minCost != LONG_MAX)
            printf("%d %lld\n", i, vertices[i].minCost);
    }
 
    return 0;
}

#include <stdio.h>

#include <vector>

#include <climits>

using namespace std;

struct Vertex

{

long long minCost;

};

struct Edge

{

int u;

int v;

int cost;

};

int main()

{

int v, e, s;

scanf("%d %d %d", &v, &e, &s);

//VERTICES

Vertex * vertices = new Vertex[v + 1];

for (int i = 0; i <= v; i++)

vertices[i].minCost = LONG_MAX;

//EDGES

Edge * edges = new Edge[e];

for (int i = 0; i < e; i++)

{

scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].cost);

}

//BELLMAN-FORD

vertices[s].minCost = 0;

long long newCost;

//relax edges

for (int i = 0; i < v; i++)

{

for (int j = 0; j < e; j++)

{

if (vertices[edges[j].u].minCost == LONG_MAX)

continue;

newCost = vertices[edges[j].u].minCost + edges[j].cost;

if (vertices[edges[j].v].minCost > newCost)

vertices[edges[j].v].minCost = newCost;

}

//check for negative cycles

for (int j = 0; j < e; j++)

{

if (vertices[edges[j].u].minCost == LONG_MAX)

continue;

if (vertices[edges[j].v].minCost > vertices[edges[j].u].minCost + edges[j].cost)

{

printf("Negative cycle");

return 0;

}

//RESULT

for (int i = 0; i <= v; i++)

{

if (i != s && vertices[i].minCost != LONG_MAX)

printf("%d %lld\n", i, vertices[i].minCost);

}

return 0;

}