Solução escrita por Enzo Dantas
Conhecimento prévio necessário:
Esse é um problema clássico e, portanto, abre espaço para diversas ideias e otimizações. Sendo assim, essa solução focará apenas na solução esperada.
Intuição
Primeiramente, imagine o que aconteceria se, de algum jeito, deixássemos o algoritmo de Dijkstra continuar rodando depois de ter achado todos os menores caminhos. O algoritmo de Dijkstra original acha o menor caminho e depois não visita mais aquele vértice, mas, tendo em mente como a ideia gulosa do Dijkstra funciona, se deixássemos ele visitar os vértices mais vezes, faz sentido pensar que ele primeiro visitaria um certo vértice com o menor caminho, depois com o segundo menor caminho, depois com o terceiro, e assim por diante.
Como implementar essa ideia?
A ideia de simplesmente deixar o algoritmo rodar funciona, mas utilizaremos a ideia de vértices auxiliares para entender o porquê. Agora não queremos apenas chegar no vértice com o menor caminho possível, queremos chegar em um vértice com o k-ésimo menor caminho 
. Perceba que não precisamos passar pelo mesmo vértice mais de 
vezes, pois os menores caminhos até o vértice 
utilizarão no máximo os menores caminhos até esse vértice. Assim, um mesmo vértice vai "conter" K vértices auxiliares - os K menores caminhos até ele. Nesse novo grafo, basta rodarmos o algoritmo de Dijkstra a partir do vértice 
(o vértice que representa o menor caminho até o vértice inicial) e imprimir a distância toda vez que passamos por um vértice 
. Perceba que chegaremos nos vértices em ordem crescente de distância, assim como foi pedido no enunciado.
Complexidade
O algoritmo é semelhante à um Dijkstra normal com N*K vértices, então a complexidade pode ser estimada em 
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.