A problem about weighted graphs

Правка en2, от 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.


Теги 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)