A problem about weighted graphs

Правка en1, от Dalisyron, 2016-03-10 14:17:46

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.

Теги shortest path, single source, graph theory, algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Dalisyron 2016-03-10 16:23:11 12 Tiny change: 'preciated.' -> 'preciated.\n\nN<=500\n'
en1 Английский Dalisyron 2016-03-10 14:17:46 334 Initial revision (published)