nhphuc's blog

Dijkstra algorithm and its variants
By nhphuc, history, 4 months ago, In English

I see that dijkstra (and some shortest path algorithm) have a lot of variants like the roads have color, money and time to pass on a road,... etc. So, how to I practice them and how should I thinking for these problem.

Anyone please help me, I'm very need a help now, my national team selection contest is coming.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Unclear question, to be frank. Are you sure you are capable of formulating the problems?

To me, most variants are just using common sense to generalize and/or add extra constraints into the shortest path traces.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    tbh, I didn't think that I'm weak in shortest path problem, but now I'm stucking in some problems using dijkstra with extra constraints so I just want to ask that how to I practice and thinking in these problems

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The catch is that you can't articulate exactly what you're stuck at, or it's just you feel like you feel alienated every single time something steps out of the comfort textbook zone, so I don't think I could provide any proper advice.

      Anyway imo, as long as a problem can be solved in Dijkstra, then there always exists a way to construct a graph catering to what I need — graph construction sometimes matters more than the algorithm used in it.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        it's like I'm stucking at how to make a claim to solve the problem, like now I have the shortest way from $$$1$$$ to $$$u$$$ then how to change state from $$$u$$$ to $$$v$$$, how to optimize it,... and if you are Vietnamese, I can send to you the statement of problem which I stucking in

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          If you feel like it, go ahead. Just a slight disclaimer, I'm not in my prime days anymore, and I don't do CP the same way high schoolers do, so I myself might get stuck as well.

          → Reply
»
4 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Practice dp problems.

I always thought of BFS/dijkstra as doing dp on a problem where there’s no proper order to process the states (i.e. no acyclicity). Then, Dijkstra basically says: ‘process states in increasing order of dp value and you’ll be fine’.

If you find that this situation is correct for a specific problem, then it’s a ‘Dijkstra problem’. You don’t need to model the problem as a graph or some bs like that, just make the observation and implement it naturally as you’d do any other dp problem.

Again, this way of thinking is in fact more powerful than Dijkstra itself. For example, it can be a different correct order of states, and you have a better chance to find it like this rather than trying to relentlessly write circles and lines on a piece of paper.

→ Reply