Dalisyron's blog

A problem about weighted graphs
By Dalisyron, history, 9 years ago, In English

Problem :

Given a weighted directed graph with both negative and positive edges, Find a path from vertex 1 to n, in which minimum subpath weight(starting from vertex 1) is maximum.

I can't think of any graph algorithm that can help me solve this problem, so any suggestions are appreciated.

N<=500

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

constraints?

→ Reply
»
9 years ago, # |
  Vote: I like it -14 Vote: I do not like it

easi task

→ Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Binary search for the answer plus BFS to check if it's possible. Details: think.

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

    I've never heard of BFS on weighted graph ... how would that be done ?

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

      I parsed "subpath" as "edge"...

      If they're paths from vertex 1, it's modified Dijkstra (you only have to ignore possible paths with length < checked answer).

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

        I used a combination of Dijkstra & DP and it worked. Thank You Xellos

        → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Could you please post the question link? I would like to solve it too.

Thanks in advance :)

→ Reply