c++graph-theorybellman-ford

What is wrong in my implementation of Ford-Bellman algorithm?

I am trying to solve the following task:

Given a directed weighted graph with edges whose weight can be negative. Find the length of the longest path from the first to the last vertex. If such a path does not exist, output ":(". If such a path is infinitely long, output ":)".

My code works correctly for 21 test cases out of 22. The problem is that I can't pick the tests for which the code is not working correctly. Here is my code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node
{
    int val = 0;
    bool isNull = true;
};

struct Edge
{
    int from;
    int to;
    int cost;
};

int main()
{
    int n, m;
    cin >> n >> m;

    vector<Node> nodes(n);
    vector<Edge> edges(m);

    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;
        edges[i] = { from - 1, to - 1, cost };
    }
    nodes[0].val = 0;
    nodes[0].isNull = false;

    for (int i = 0; i < max(nodes.size() - 1, (vector<Node>::size_type)1); i++)
    {
        for (auto [from, to, cost] : edges)
        {
            if (!nodes[from].isNull && (nodes[to].isNull || nodes[to].val < nodes[from].val + cost))
            {
                nodes[to].isNull = false;
                nodes[to].val = nodes[from].val + cost;
            }
        }
    }

    if (nodes.back().isNull)
    {
        cout << ":(";
        return 0;
    }

    for (auto [from, to, cost] : edges)
    {
        if (!nodes[from].isNull && nodes[to].val < nodes[from].val + cost)
        {
            for (int i = 0; i < max(nodes.size() - 1, (vector<Node>::size_type)1); i++)
            {
                for (auto [from, to, cost] : edges)
                {
                    if (!nodes[from].isNull && nodes[to].val < nodes[from].val + cost)
                    {
                        if (to == nodes.size() - 1)
                        {
                            cout << ":)";
                            return 0;
                        }

                        nodes[to].val = nodes[from].val + cost;
                    }
                }
            }
        }
    }

    cout << nodes.back().val;

    return 0;
}

Also I know, that the correct answer for the test that the program failed is ":)", because I tried to send a program, which outputs ":)" in all cases, and it passed this test (but, obviously, did not passed lots of other). That means that the problem is probably in the part of program, which checks when to output ":)".

So the question is: what is wrong in my code?

Edit: it is guaranteed, that 1 <= n <= 2000, 1 <= m <= 10000. Also I have no access to the test cases

Edit: here is an original problem https://www.eolymp.com/uk/problems/1454

Solution

  • Your implementation is incomplete.

    What you've certainly learned is (for shortest path. Longest is the same with opposite cost), is that Dijkstra algorithm works only with positive weight, while Ford works even when weight might be negative. So, in your case, just reverse words: Dijkstra works only with all negative weight, while Ford works even if some weight are positive.

    But usually, the second part of this sentence is: « if there are no absorbing cycle » (aka negative cycle). If there is a negative cycle then a longest path doesn't exist. Not because there isn't any path at all. But because there is an infinity of them.

    Analogy: the maximum value of a set (max({1,2,3})=3) may not exist for two different reasons:

    Same goes here: longest path may not exist for two different reasons

    Take this graph enter image description here

    Without cycling longest path is Start→I→End (cost: 20)

    Path, going through A cannot be longer. Start→A→B→C→D→End cost 1. Existence of cycle B→C→D→B isn't a problem. Because it doesn't augment the total weight. Start→A→B→C→D→B→C→D→End cost -1. Start→A→B→C→D→B→C→D→B→C→D→End -3, etc. Each loop in the cycle shorten the path, so, no path is longer than 20 on this side.

    But path going through E is another story.

    Start→E→F→G→H→End has total weight 5. But if you loop in the cycle F→G→H→F,
    Start→E→F→G→H→F→G→H→End is 8.
    Start→E→F→G→H→F→G→H→F→G→H→End is 11.
    Etc. Each loop in the cycle is a longer path
    Start→E→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→End is 23. And beats the longer path. But it is not the longer. And what ever "longer path" you can imagine, I just have to add a F→G→H→ in it to make it even longer

    You say Start→E→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→End is longest (size 32)?. Well Start→E→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→F→G→H→End is size 35

    Etc.

    So, you see the point: there is no longest path, because there is always a longer one. There is no boundary.

    You have to detect these situations, to return the information that there is no longest path.

    The Bellman-Ford (for shortest path, that you adapted for longest path) is usually

    cost(*)=∞ but for cost(Start)=0
For (at least) n-1 times:
    For all edges (A,B):
        If cost(A)+weight(A,B) < cost(B):
            cost(B) = cost(A)+weight(A,B)
            predecessor(B) = A

For all edges(A,B):
    If cost(A)+weight(A,B) < cost(B):
        return "NoShortestPath"

    So, algorithm is just n-1 iterations on all edges, checking it an edge can improve a cost, and doing so if it does.

    And the last 3 lines, are just a nth iteration. Bellman-Ford says that never more than n-1 iterations are necessary to find shortest path... if it exists (because in a graph with n vertices, a path passing exactly once through each vertex would traverse n-1 edges. So a path of n edges has to pass twice through at least one vertex. So one cycle. So, if that cycle is positive, you could shorten the path by removing the cycle, and that is a path you have already seen before. And if that cycle is negative, then, there isn't any shortest path).

    So if a nth iteration would change something, that means that there is no shortest path.

    You forgot those 3 lines. That is that nth iteration to check if, after n-1 iterations, it is still possible to improve a cost. If yes, you are in that "no best path exist, because there is always an even better one" situation.

    I let you translate that in your C++ (and transpose to "longest path" problem)