009 Algoritmul lui Dijkstra

[•depevlad]

Pentru cei ce vor sa inteleaga algoritmul lui Dijkstra si poate nu au inteles din sursa data in explicatii, aici este implementarea mea de 100 de puncte, scrisa clar si explicata prin comentarii. Implementarea foloseste priority_queue.

http://pastebin.com/xTgRuZKn

Sper sa fie de ajutor!  

[•zelmoatis]

eu nu inteleg de ce pe primul test, si anume:

7 9
1 4 2
1 2 1
2 3 3
4 3 1
3 5 2
5 6 5
6 3 1
3 7 2
1 5 9

avem fisierul cu output "corect"

1 3 2 5 10 5

asta insemnand ca distanta minima de la primul nod la al saselea ar fi de 10
totusi mie mi se pare ca distanta mai scurta ar fi prin 1-4,4-3,3-6, cu un cost total de 4

[•zelmoatis]

eu nu inteleg de ce pe primul test, si anume:

7 9
1 4 2
1 2 1
2 3 3
4 3 1
3 5 2
5 6 5
6 3 1
3 7 2
1 5 9

avem fisierul cu output "corect"

1 3 2 5 10 5

asta insemnand ca distanta minima de la primul nod la al saselea ar fi de 10
totusi mie mi se pare ca distanta mai scurta ar fi prin 1-4,4-3,3-6, cu un cost total de 4

[•zelmoatis]

ok, nvm, tocmai am aflat ca graful era orientat 

[•dragon]

Poate ma lamureste si pe mine cineva.

Sa luam, spre exemplu testul 1.
Date de intrare:
7 9
1 4 2
1 2 1
2 3 3
4 3 1
3 5 2
5 6 5
6 3 1
3 7 2
1 5 9

Date de iesire:
1 3 2 5 10 5
Daca pana la nodul 3 distanta minima e 3 (de acord), iar intre 3 si 6 exista drum de lungime 1, de ce drumul minim pana la 6 e 10(mie imi da 4)?
Multumesc anticipat!!

[•hiimsoba]

@dragon, Graful este orientat. Ai arc de la nodul 6 la nodul 3, nu există arc de la 3 la 6 care să aibă costul 1. Implementarea ta probabil că folosește un graf neorientat. :)