A problem about weighted graphs

Revision en2, by Dalisyron, 2016-03-10 16:23:11

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.


Tags shortest path, single source, graph theory, algorithms


  Rev. Lang. By When Δ Comment
en2 English Dalisyron 2016-03-10 16:23:11 12 Tiny change: 'preciated.' -> 'preciated.\n\nN<=500\n'
en1 English Dalisyron 2016-03-10 14:17:46 334 Initial revision (published)