tasyrkin's blog

A solution for a graph problem
By tasyrkin, 10 years ago, In English

Hello everybody!

Recently I have faced the following graph problem: Given a directed graph with nonnegative weights. There is a need to find a number of paths between two nodes which path's weights are less then specified number. Graph may contain cycles and path may contain cycles.

I have found the Yen's algorithm which can find K shortest paths and which may be adjusted to partially solve my problem (the algorithm finds loopless paths) and wondering now if there is an approach to solve the problem.

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use simple DP where r[v][k] = number of paths from v to end with weight <= k

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

    Well, that's only if the weights are small numbers? In general with weights like 10^9 this DP will be horrible.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      It looks like author have forgotten to specify limits so it is not clear whether simple DP or simple DFS or something else was intended to be used...

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        There is no limits for a problem, but they may be set as soon as identified. How would you solve such problem with DFS?

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give a link to the problem.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In fact, your problem is NP-hard, because it's possible to reduce the longest path problem to it in polynomial time.

→ Reply