How can i modify Bellman-ford to account for this restriction?:

  • only allowed a certain number of edge-traversals (k) to go from source-node to target-node?

The algorithm runs on graphs with:

  • 0, 1 or multiple negative and non-negative edges and cycles.

I am given:

  • k: max number of edges allowed
  • n: total number of nodes
  • m: total number of edges
  • e: list of all edges (from, to, weight).
  • v: source node
  • t: target node

My Code (Java):

int[] d = new int[n]; // Array of distances from v to other vertices.
int[] p = new int[n]; // Array of predecessors.

// Populates d with all inf, except at index v.
    for (int i = 0; i < n; i++) {
        if (i == v) d[i] = 0;
        else d[i] = INF;
    }

    int x = 0;

// Relaxing of edges. 
    for (int i = 0; i < n-1; ++i) {
        x = -1;
        for (int j = 0; j < m; ++j) {
            if (d[e[j].from] < INF) {
                if (d[e[j].to] > d[e[j].from] + e[j].weight) {
                    d[e[j].to] = Math.max(-INF, d[e[j].from] + e[j].weight);
                    p[e[j].to] = e[j].from;
                    x = e[j].to;
                }
            }
        }
    }

// Negative cycle detection.
    if (x == -1) {
        System.out.println("Negative cycle detected");
    }
    else {
        int y = x;
        for (int i = 0; i < n; ++i) {
            y = p[y];
        }
        ArrayList<Integer> path = new ArrayList<Integer>();
        for (int cur = y; ;cur=p[cur]){
            path.add(cur);
            if (cur == y && path.size() > 1) {
                break;
            }
            Collections.reverse(path);
        }
        System.out.print("Negative cycle: ");
        for (int i = 0; i < path.size(); ++i) {
            System.out.print(path.get(i) + " ");
        }
    }

    return d[t];

I would appreciate suggestions on how to add k-most edge restrictions to this.

  • Hint, add a parameter to record how many edges you have travelled. (hmm, unregistered user...) – Apass.Jack Dec 2 at 14:11
  • @Apass I don't think Bellmon will work if each edge traversed $< |V| - 1$ times. – Mr. Sigma. Dec 2 at 14:14
  • @Mr.Sigma, "only allowed a certain number of edge-traversals (k) to go from source-node to target-node". If $k=1$ and $|v|=3$, what are you going to do? I doubt this exercise has anything to do with Bellmon-ford. – Apass.Jack Dec 2 at 14:21
  • k is always > IvI. The idea is to take advantage of negative cycles by traversing them for as many edge-traversals, as you are allowed, but not exceeding k. – supboi Dec 2 at 14:42
  • If $k$ is indeed always greater than $|v|$, please add that condition in the question. – Apass.Jack Dec 2 at 14:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.