Поиск k кратчайших путей ориентированном графе.

Revision ru2, by sergileon, 2015-11-18 09:42:15

Требуется найти k кратчайших путей в ориентированном графе от одной вершины до другой (обе вершины заданы). Веса положительные. N < 1000, M = n * 4, k = 10. Может знает кто-нибудь, как решить данную задачу? Пока мои размышления свелись к следующему: найти первый кратчайший путь Дейкстрой, затем искать следующие пути без одного ребра из найденного пути. Так получится найти второй путь. А дальше тупик.

Tags графы, кратчайшие пути

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian sergileon 2015-11-18 09:42:15 50
ru1 Russian sergileon 2015-11-17 15:47:28 402 Первая редакция (опубликовано)