Proving that the Bellman-Ford algorithm contains negative circuit

Let $ D=(V,B), n=|V|$ be a directed graph. Then the graph contains a circuit of negative length from $ s$ if and only if $ f_n(v) \neq f_{n-1}(v),$ where $ v \in V,$ and $ f_k(v)=$ min$ \{l(P)|P$ is an $ s-v$ walk traversing at most $ k$ arcs }.

I do not understand what a $ s-v$ walk means and what is the meaning of the function $ f_n$ .

Can somebody help me prove the two directions of the above statement ? Many thanks.

Bellman-Ford algorithm implemented with queues in C

I am in the midst of applying a bellman ford algorithm using a queue and my code works for all cases where the source vertex is 0 however outputs garbage when the source vertex is changed. I think there must be an issue with the line “foredge;edge<(nn);edge);” Thanks.


include

include

include

int readGraphWeighted(int n, int m, int graph[]){ int i; int size = n*n; for(i = 0; i < size; i++){ graph[i] = 0; }

int edgeA; int edgeB; int weight; for(i = 0; i < m; i++){ scanf(“%d %d %d”, &edgeA, &edgeB, &weight); graph[edgeA*n + edgeB] = weight;

} }

int findVal(int element, int queueSize, int queue[]){

//if element is in the queue then function returns 0 //else it returns 1 int i; int toReturn=1; for(i=0;i<queueSize;i++){     if(element==queue[i]){         toReturn=0;     } } return toReturn; 

}

int main(){

//initialize all necessary int n; int m;  scanf("%d %d",&n,&m);   int d[n]; int p[n]; int graph[n*n]; int queue[n]; int source; int edge; int queueSize=0; int head=0;   //intermediary variables int i; int row; int col;  //read in all information needed readGraphWeighted(n,m,graph); scanf("%d",&source);  //intialize everything as instructed for(i=0;i<n;i++){     d[i]=INT_MAX;     p[i]=-1;     queue[i]=0; }  queue[head]=source; queueSize++; d[source]=0; p[source]=source;  //**main body of program**   while(queueSize !=0){     //pop     edge=queue[head];     queueSize=queueSize-1;     head++;      //for every edge     for(edge;edge<(n*n);edge){          if(graph[edge] !=0){             //if we reach a value in graph record its row and col             row=edge/n;             col=edge%n;              //if the value in d is larger replace it             if(d[col]>d[row]+graph[edge]){                 d[col]=d[row]+graph[edge];                  //update predecessor                 p[col]=row;                  if(findVal(col,queueSize,queue) == 1){                      //push                     queue[queueSize-1]=col;                     queueSize++;                 }             }         }     } } printf("\nRESULTS:\nsource vertex: %d\n",source); printf("D: "); for(i=0;i<n;i++){     printf("%d, ",d[i]); } printf("\n"); printf("P: "); for(i=0;i<n;i++){     printf("%d, ",p[i]); } 

}


Why does Bellman-Ford algorithm use < rather than ≤?

The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle?

For instance, say I have the below example going from initialization state through the first iteration and on to the second.

Initial state

    (0)S----(1)----B(inf)         \         /         (1)    (-1)             \     /            \   /               C(inf) 

First iteration

...Check edges... S->B D[S] + 1 < D[B] = 0 + 1 < inf => True => Update D[B]  B->C D[B] + (-1) < D[C] = 1 + (-1) < inf => True => Update D[C]      (0)S----(1)----B(1)         \         /         (1)    (-1)             \     /            \   /               C(0) 

Second iteration when checking for negative cycles

...Check edges... ...Skipping to check B->C... B->C D[B] + (-1) < D[C] = 1 + (-1) < 0 => False         (0)S----(1)----B(1)         \         /         (1)    (-1)             \     /            \   /               C(0) 

Shouldn’t the last check between B->C be true to detect the negative cycle? i.e. Shouldn’t we use less-than-or-equal-to (≤) rather than (<)?

Modifying relaxation for the Bellman-Ford algorithm

I’m using the Bellman-Ford algorithm to find the best path in my graph. However, instead of choosing the path with the lower value, I want to choose the path with the highest value. And instead of using the sum of all edges as a length of a path, I want to use the following formula: lengthOfPath = sqrt(a^2 - b^2) for each edge, where a is the edge we are coming from, and b is the edge we are arriving to.

Basically, the formula represents the number of units left in our army after conquering a city, so logically, we want to choose the path with the least casualties.

My idea was to use the Bellman-Ford algorithm and rewrite the relaxation so it works according to our rules. I’m using a custom library for graphs and I already created a graph g, added all cities as vertices and set the weight of an edge between a & b is the size of our military, while the weight of an edge between b & a is the size of enemy military guarding the city, where a & b are our vertices (cities).

I used the following code (g is our graph, getVertices() and getEdges() returns a set of all vertices and edges, getSource() and getTarget() returns a source or target vertex of an edge etc..):

public Map<Vertex, Double> bellmanFord(Vertex s) {         Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);         d.put(s, 0d);         for (int i = 0; i < g.getVertices().size(); i++)                 for (Edge e : g.getEdges())                         relax(e, d);         return d; }  public void relax(Edge e, Map<Vertex, Double> d) {         Vertex u = e.getSource();         Vertex v = e.getTarget();         if (d.get(u) + e.getWeight() < d.get(v))                 d.put(v, d.get(u) + e.getWeight()); } 

And below is my modified code for the relaxation:

public void relax(Edge e, Map<Vertex, Double> d) {         Vertex u = e.getSource();         Vertex v = e.getTarget();         if (d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight()) > d.get(v))             d.put(v, d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight())); }  public double formula(double ourCity, double enemyCity) {         double a = Math.pow(ourCity, 2);         double b = Math.pow(enemyCity, 2);         double result = a - b;         return Math.sqrt(vysledok); } 

However, using my modified code for relaxation the Bellman-Ford is not working correctly. It always returns a map with all values set to infinite. Could you help me fix my problem?

Thanks

Bellman-Ford – is number of interations greater than diameter?


Diameter of a connected, undirected graph is the smallest natural number d, so that between any two vertices of the graph exist path of length at most d.

Prove or disprove: in Bellman-Ford is the number of iterations always equal or lower than d.

I’m trying to solve this issue. What I tried was sketching a lot of graphs, however I have failed to find a single graph where the number of iterations would be higher than the diameter.

The only graph where the number of iterations wouldn’t be <= than diameter would be a graph with negative edges, however I found out that in undirected graph there can’t be any negative edges, otherwhere there would be a negative cycle.

So, AFAIK the statement is correct. However, how would I prove such a statement? I don’t even know how to start. Thanks for any help

How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

The Bellman-Ford algorithms on a graph with n vertices, normally includes a loop executed n-1 times. Each time through the loop we iterate over the list of edges (u,v) and relax v. Note that we don’t relax u and v on each iteration through the edges.

What I don’t understand is that if G is an undirected graph with n vertices, then it is equivalent to a directed graph with 2n vertices. We simply think of the edge between u and v as a set {u,v} for an undirected graph, and as the ordered pair (u,v) for a directed graph.

I don’t understand why the Bellman-Ford algorithm needs only n-1 repetitions for both a directed and undirected graph. It seems like it should take n-1 repetitions for directed graph, and 2n-1 repetitions for undirected graphs or we should relax both vertices of an edge on each iteration.

Otherwise stated, why does running Bellman-Ford on a directed graph, also find the shortest paths of the undirected graphs?