Algorytm Dijkstry i błąd w implementacji (c++)
Ostatnio zmodyfikowano 2014-11-23 22:15
anonim Temat założony przez niniejszego użytkownika |
Algorytm Dijkstry i błąd w implementacji (c++) » 2014-11-23 22:15:09 Cześć W ramach ćwiczeń algorytmiki wziąłem się za Dijkstrę http://informatyka.wroc.pl/node/406?page=0,4 Tu macie kod(tylko dijkstra): #include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
vector < int > cost;
int INFINITY = 1000000000;
vector < vector < pair < int, int > > > v;
void dijkstra( int s, int n ) {
cost.clear();
cost.resize( n, INFINITY );
priority_queue < pair < int, int > > q;
q.push( make_pair( cost[ 0 ], s ) );
cost[ s ] = 0;
while( !q.empty() ) {
pair < int, int > p = q.top();
q.pop();
int vert = p.second;
int dist = p.first;
for( int i = 0; i < v[ vert ].size(); i++ ) {
if( cost[ v[ vert ][ i ].first ] > cost[ vert ] + v[ vert ][ i ].second ) {
cost[ v[ vert ][ i ].first ] = cost[ vert ] + v[ vert ][ i ].second;
q.push( make_pair( cost[ v[ vert ][ i ].first ], v[ vert ][ i ].first ) );
}
}
}
}
Jednak to nie działa W założeniu dla wierzchołka startowego s i n wierzchołków funkcja ma wypełnić tablicę cost odległością od s do i-tego wierzchołka Mam jeszcze pytanie, czy priority_queue jest odpowiednim kontenerem? Bo jeżeli pod koniec dodaję nową parę (odległość do wierzchołka, wierzchołek), tu już mogę mieć w kolejce parę o tym samym wierzchołku, ale innej odległości. (najlepiej byłoby sparawdzić czy taka jest, jeżeli tak to ją usunąć i wstawić od nowa) niestety priority_queue z stl nie obsługuje takich funkcji Myślałem też, żeby odległość (pair.first w kolejce) trzymać jako wskaźnik, żeby to się automatycznie aktualizowało, ale to chyba tak nie działa |
|
| « 1 » |