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.

N<=500

Tags shortest path, single source, graph theory, algorithms

History

 
 
 
 
Revisions
 
 
  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)