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

Shortest path in a weighted graph(if many then lexicographically smallest)
Автор fluffy_x, история, 6 лет назад, По-английски

How to find the shortest path in a weighted graph(**if many then lexicographically smallest**) using Dijkstra? — I am getting WA on 2 test cases - Problem link :Your text to link here... - Although this can be solved using BFS, but I want to know do when the graph is weighted?

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

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

Let's assume X = 1. Using Dijkstra, calculate the distance Dv from node 1 to node v. For every node u, store Pu, the minimum v over all edges (v, u) such that Dv + w(v, u) = Du. It is easy to find this path now:

std::vector<int> find_path(int v) {
	std::vector<int> ans;
	for(ans.push_back(v); v != 1; ans.push_back(v = p[v]));
	std::reverse(ans.begin(), ans.end());
        return ans;
}
→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Got it!

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

    Your solution is wrong. Consider this graph:

    6 6 1 2 1 1 4 1 4 3 1 3 6 1 5 6 1 2 5 1

    According to you shortest + lexographically shortest path will be 1 -> 4 -> 3 -> 6 while it should be 1 -> 2 -> 5 -> 6;

    → Ответить