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.
Binary search for the answer plus BFS to check if it's possible. Details: think.
I've never heard of BFS on weighted graph ... how would that be done ?
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).
I used a combination of Dijkstra & DP and it worked. Thank You Xellos
Could you please post the question link? I would like to solve it too.
Thanks in advance :)