Блог пользователя judaybhaskerreddy

help needed for cses prbm(calculating the time complexity for k shortest loopy paths)
Автор judaybhaskerreddy, история, 2 года назад, По-английски

i solved cses(graph) flight paths qn( https://cses.fi/problemset/task/1196 ), there is an explanation given in gfg(https://www.geeksforgeeks.org/1st-to-kth-shortest-path-lengths-from-node-1-to-n-in-given-graph/) i couldnt find out how they calculated the time complexity as O((n+m)klogk)) cuz i am getting a diff time complexity...can some one explain how did they come up with that time complexity.....thanks in advance..

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your URL broken, you put ) at the end of URL

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In standard dijkstra's, we maintain the shortest route. In this problem, we'll only consider the k shortest path to reach each vertex. It could be save in 2-dimension array dist[n][k] where dist[i][j] is the j shortest path to reach vertex i. The initial state is dist[1][1] = 0. We can find the result by modifying dijkstra a little bit. My submission

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i got the AC for the qn but the thing is how did the time complexity for the problem became O((n+m)klogk) as given in gfg i got a different result...what is the time complexity did you get

    → Ответить