There are several cities 1,2,3,4,5,6,7,8 ... but there is no direct route between each one. To get to the 8th from the 1st, you need to go through 3.5 and 6th. How to find the shortest route?

  • Your attempt at solving the studio! - user207618
  • I did not try to solve it, the algorithm is interesting to me - emtecif

2 answers 2

This is a classic graph problem. It is solved using the Dijkstra algorithm.

  • Why immediately Dijkstra, here the graph is not weighted, the usual BFS is enough. - pavel
  • @pavel is a weighted graph, all edges weigh 1. BFS will find all routes, then you will have to look for the best one among them. - gbg
  • not really, just Dijkstra's complexity at least N log N and even N^2 and frontal BFS works for N And to search not all routes, but only 1 most (it will be optimal). - pavel
  • @pavel, bfs works for O (n + m) or O (n ^ 2) depending on the implementation. Dijkstra for O (n ^ 2). For O (n * lb (n)) there seems to be a similar algorithm, but this is not really a dextra. - Qwertiy ♦
  • @gbg, bfs is just looking for the best. - Qwertiy ♦

The problem can be solved using the algorithm A *