serega.belarus's blog

Ford-Bellman algorithm
By serega.belarus, 11 years ago, In English

Good day! I'm interested in the solution of the following problem via Ford-Bellman algorithm, because I only solved the one via Dijkstra. But my solution was not enough successful (4 tests of 13 passed).

My code.

Statement of the problem:

Any suggestion?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

So, why don't you subtract 500 from length of every edge? It's not correct to subtract it only in the end because you don't know the length of the shortest path in advance.

Let me give an example: say you have found a path with length 3000 with 5 edges. So you output 3000 — 5 * 500 = 500. But if there exists a path with length 3200 with 6 edges, it would give 3200 — 6 * 500 = 200. Which is better. But you only find the first one because without the subtracted 500 from every edge it is shorter.

→ Reply