Bellman Ford does not work

general
, ,
1

I am trying to solve the following problem:

Problem link

Here, we have a path between any two nodes using the euclidean distance between them.

For finding the shortest path, I am trying to use bellman ford algorithm as follows:

pair array p contains x and y coordinates of all nodes.
p[0] represents source node, and p[n + 1] is the destination.

Implementation :

Here is my code :

http://ideone.com/IFzUIx

Input :

2

6

8 2

4 0

8 0

4 -1

7 -1

6 -2

2 1

9 2

1

0 0

-1 1

1 -1

The required output is:

20

4

but my program generates :

26

4

for the sample cases

Please say if I have correctly used bellman ford here. I tried using dijkstra algorithm for the same problem, and it gives correct output. Why does Bellman Ford fail then?

2

Well, you didn’t implement bellman-ford algorithm correctly, check Bellman-Ford for more details.

1 Like
3

well i found my mistake, thanks!!
and here e = (num_of_nodes)^2

so can’t I use Bellman Ford here to get my code AC?

4

Bellman-Ford’s worst case complexity is O(|V||E|).
Here there is nothing restricting you from moving from one point to another so, the number of edges would be = |V| choose 2, rendering a regular implementation of Bellman-Ford to run in O(|V|^3) which is too slow considering that |V| <= 2500.

1 Like
5

means I can’t use regular Bellman-Ford, the only choice I have is Dijkstra, or say if something else could be done. I tried Dijkstra, but don’t want to rely totally on it because of its negative edge disadvantage.