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 :

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?