bejuzb's blog

Find min cost path between two points
By bejuzb, history, 5 years ago, In English

I've been seeing such questions for a long time now and I haven't been able to catergorize it. Hoping someone could help me here. The question contains pairs of points and a cost. You're given 1 2 C0, meaning you can go from 1 to 2 with cost C0. We have N such points and have to reach 1 to some point, say N. What's the minimum cost of it? Ex

1 2 3

2 3 1

1 3 1

3 4 2

2 4 1

In this case, you'd go from 1->3>4 with total cost 3 (1+2). How do I go about solving this?

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

Comments Comments (1)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

That a graph problem and it can be solved using Dijkstra algorithm. Dijkstra: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

→ Reply