Как найти 3 кратчайших пути в графе?
======================================

 Найти 3 самых коротких пути в графе. То есть вывести топ-3 коротких путей.  

Как исключить первый путь при поиске второго? И первые два при поиске третьего? 

 Трудно тебе будет.  

1. Находишь путь.  

2. Из этого пути поочередно удаляешь по ребру и строишь путь в графе без ребра. Один из вариантов (или несколько) будут кратчайшими. Если несколько - задача решена.  

3. Если нет - ну ты понел... 

 дейкстра 

 В каждой вершине хранить не более трёх кратчайших путей до неё. В Дейкстре использовать очередь без модификации веса. Если очередной путь, взятый из очереди, лучше третьего по порядку пути, сохранённого в вершине, (или сохранено не более двух путей) - добавляем этот путь в вершину, а все его продолжения - в очередь.  

 Проблема в том, что в путях могут появиться циклы. Например, для графа из двух вершин с тремя рёбрами  

(1,2, w=1)  

(1,2, w=3)  

(1,2, w=5)  

будут выданы пути 1-2 (по первому ребру), 1-2 (по второму ребру) и 1-2-1-2 (по первому ребру). Если циклы нежелательны - придётся возиться дольше