# How to modify Bellman-ford to account for a max-number of edge-traversals allowed

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]){
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