wyznaczenie ścieżki, algorytm dijkstry

Witam, mam problem z wyznaczeniem poszczególnych odcinków jednostkowych wyznaczonej trasy z algorytmu dijkstry, mógłby mi ktoś podpowiedzieć jak mam to zaimplementować?

int minOdleglosc(int odleglosci[], bool QS[])
{
    int minimum= INT_MAX;
    int min_index;
   for (int i=0;i<ilosc_wierzcholkow;i++)
    {
        if (QS[i] == false && odleglosci[i] <minimum)
        {
          minimum = odleglosci[i];
          min_index = i;
        }
    }
   return min_index;
}

vector <int> wyszukajSciezke(vector <vector <int> > &m_sasiedztwa,int skad, int dokad)
{
    int odleglosci[ilosc_wierzcholkow];
    bool QS[ilosc_wierzcholkow];
    vector <int> sciezka;

inicjalizacjaTablic(odleglosci,QS,skad);

    for(int i=0;i<ilosc_wierzcholkow;i++)
    {
        int u=minOdleglosc(odleglosci,QS);
        QS[u]=true;
        for(int j=0;j<ilosc_wierzcholkow;j++)
        {
            if(QS[j]==false&&m_sasiedztwa[u][j]!=0&&
                                odleglosci[u]+m_sasiedztwa[u][j]<odleglosci[j])
            {
                odleglosci[j]=odleglosci[u]+m_sasiedztwa[u][j];
                sciezka.push_back(u);
            }
        }
    }

    return sciezka;

}


};

 

Próbuje zapisywać ścieżke do vectora sciezka, jednak nie do końca działa to poprawnie. Mógłby to ktoś zweryfikować i powiedzieć gdzie robię błąd?

Pomoże ktoś? Stanąłem kompletnie z programem, a bez tego nie ruszę dalej.

Jakbyś to napisał w wersji "dla ludzi" to może być ktoś pomógł. Ale wtedy to pewnie sam być znalazł bląd. Skasuj to i napisz jeszcze raz, tym razem w sposób czytelny. Wyobraź sobie że ten algorytm wygląda tak:

struct DijkstraVertex{
    int src;
    int weight;
}
vector<int> getPath(vector <vector <int> > & adiancenceMatrix, int src, int dst){
    priority_queue<DijkstraVertex> distances = initializeDistances(adiacenceMatrix.size());
    vector<DijkstraVertex> path;
    while(!distances.empty()){
        relaxateVertex(distances.pop());
    }
    return backtracePath(path);
}

I dalej oczwiście pozostałe metody. Widzisz jaka jest różnica? Że w jednym kodzie od razu widać co się dzieje a w drugim nawet ty sam nie wiesz a jesteś autorem...

Hmm, jak mam napisać to inaczej? Ciężko mi się połapać czego oczekujesz. Wydaję mi się, że ta moja implementacja jest dosyć prosta, nie potrafiłbym inaczej tego napisać.
Nie jestem pewien w 100% co do przerywania pętli, gdyż nigdzie nie mogłem znaleźć w internecie przypadku, w którym ktoś korzystałby z algorytmu dijkstry w celu znalezienia ścieżki od punktu a do b, a jedynie do wszystkich punktów. Testowałem już ten algorytm na wiele sposobów i nie mogę do tego dojść.

Bo ten algorytm do tego nie sluży o_O Jak przerwiesz pętlę to możesz dostać rozwiązanie nie-optymalne po prostu. Jak już bardzo chcesz liczyć szybciej to A*. To jest modyfikacja Dijkstry która stosuje pewną heurystykę w wybieraniu wierzchołków. W przypadku poruszania sie po mapie 2d można jako heurystykę stosować kierunki, tzn wybierać wierzchołki "w kierunku" celu.

W takim razie jak mam wyszukać ścieżke z punktu a do b (algorytm dijkstry)? I w przykładzie który pokazałeś wyznaczana jest jedynie ścieżka, a mi zależy jeszcze na odległości.

No to odległość będzie równa liczbie tych "kafelek" (wierzchołków na liście wynikowej).

Jak to odleglość będzie równa liczbie kafelek? Przeciez do tablicy tej ścieżki zapisuje numery wierzchołków, a nie wagi, a wagi biore z macierzy sasiedztwa.

Ludzie zlitujcie się i pomóżcie..

Minęło dopiero 2.5h, spokojnie :P
Zacznij od sformatowania tego swojego kodu.

Błąd w algorytmie byłby oczywisty gdybyś go po ludzku napisał, no ale ok... Twoje budowanie ścieżki jest zrobione po prostu źle. Dodajesz do swojej "ścieżki" każdy zrelaksowany wierzchołek co totalnie nie ma sensu. Ścieżkę możesz wyznaczyć dopiero PO wyliczeniu odległości od wierzchołka do źródła. Po to też potrzebna mi była struktura która przechowuje oprócz kosztu dojścia do wierzchołka także "poprzednika". Dijkstrę stosujesz żeby policzyć jaki jest minimalny koszt dojścia z wierzcholka X do każdego innego wierzchołka w grafie. Ale dla każdego wierzchołka musisz pamiętać "z którego wierzchołka tam przyszedłeś" (czyli kiedy relaksujesz i wychodzi ci że drogą do danego wierzchołka jest krótsza przez inny wierzchołek to zapisujesz ten inny wierzchołek).

Dzięki temu na koniec wyliczasz ścieżkę idąc od końca. Zaczynasz w wierzchołku końcowym, wyciągasz sobie jego "poprzednika", następnie poprzednika poprzednika itd aż dojdziesz do źródła.

W tej chwili algorytm wyszukuje odleglości od jakiegoś wierzchołka "stad" do wszystkich wierzchołków. W którym momenice powienienem przerwać pętle szukając odległość tylko do konkretnego wierzchołka "dokad"?

Ścieżkę możesz wyznaczyć dopiero PO wyliczeniu odległości od wierzchołka do źródła.

Mógłbyś mi to dokładniej wytłumaczyć? Myślałem, aby utworzyć tablicę, w której i-ty element(i=nr wierzchołka) będzie zawierał wierzchołek swojego poprzednika, tylko nie wiem jak to dodać do kodu.

I nie obejdę się jednak bez tej struktury?
Mógłbyś mi to jakoś prościej wytłumaczyć na fragmentach kodu, bo sam chyba nie poradzę sobie z tym.

Struktury są po to żeby ci bylo łatwiej a nie trudniej! Jakbyś miał tablicę takich struktur zamiast gołej tablicy intów odleglosci to mógłbyś zrobić

            if(QS[j]==false&&m_sasiedztwa[u][j]!=0&&
                                odleglosci[u].weight+m_sasiedztwa[u][j]<odleglosci[j].weight)
            {
                odleglosci[j].weight=odleglosci[u].weight+m_sasiedztwa[u][j];
                odleglosci[j].src = u;
            }

I voila, pamiętasz nie tylko nową wagę dla wierzchołka j ale też że przyszedłeś tam z wierzchołka u.

bo sam chyba nie poradzę sobie z tym.

Spoko, wykształcenie nie piwo, nie musi być pełne. Zresztą na świecie potrzeba też wielu piekarzy i fryzjerów, coś dla siebie znajdziesz :)

A w którym momencie przerywać działanie pętli aby wyszukiwał mi tylko do jakiegos wierzcholka "dokad"?

Kiedy do niego dojdziesz? o_O

Czyli w pierwszej pętli for, bo właśnie mi nie działa...

 
 for(int i=0;i<=dokad;i++)
    {
        int u=minOdleglosc(odleglosci,QS);
        QS[u]=true;
        for(int j=0;j<ilosc_wierzcholkow;j++)
        {
            if(QS[j]==false&&m_sasiedztwa[u][j]!=0&&
                                odleglosci[u]+m_sasiedztwa[u][j]<odleglosci[j])

Jak zrobić aby do tablicy 'odleglosci' zapisywana byla jedynie sciezka od wierzcholka 'skad' do wierzcholka 'dokad' ?
Bo chyba można tak zrobić, dobrze myślę? Czy do tego muszę utworzyć kolejną tablicę?

Moja rada: weź kartkę papieru do ręki i wykonaj na tej kartce twój algorytm...

Wydaję mi się, że w drugiej pętli for powinienem zrobić warunek przerywający działanie pętli np:

if(j==dokad)
break;

Czy dobrze myślę?
Jednak wtedy i tak do tej tablicy odleglości zapisywane są ścieżki poboczne, a mi chodzi tylko o wyznaczenie ścieżek prowadzących od punktu a do b.

Przepisałem ten twój kod na wersję bardziej dla ludzi.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

const int maxWeight = 100000;

struct DijkstraVertex{
	int id;
    int src;
    int weight;
    int toProcess;
    DijkstraVertex(int i, int w=maxWeight):id(i),src(-1),weight(w),toProcess(true)
    {}
};

vector<DijkstraVertex*> prepareVertices(int src, int size){
	vector<DijkstraVertex*> vertices;
	for(int i=0;i<size;i++){
		if(i==src){
			vertices.push_back(new DijkstraVertex(i,0));
		}else{
			vertices.push_back(new DijkstraVertex(i));
		}
	}
	return vertices;
}

bool pathExists(const vector<int>& pathsFromVertex, int i) {
	return pathsFromVertex[i] != 0;
}

int newCost(const vector<int>& pathsFromVertex, int i, DijkstraVertex* vertex) {
	return vertex->weight + pathsFromVertex[i];
}

bool betterCostPath(const vector<DijkstraVertex*>& vertices, int i,
		const vector<int>& pathsFromVertex, DijkstraVertex* vertex) {
	return vertices[i]->weight > newCost(pathsFromVertex, i, vertex);
}

void relaxateVertex(DijkstraVertex* vertex, vector<vector<int> >& adiacenceMatrix, vector<DijkstraVertex*>& vertices){
	vector<int> pathsFromVertex = adiacenceMatrix[vertex->id];
	for(unsigned int i=0;i<pathsFromVertex.size();i++){
		if (pathExists(pathsFromVertex, i) && betterCostPath(vertices, i, pathsFromVertex, vertex)) {
			vertices[i]->weight = newCost(pathsFromVertex, i, vertex);
			vertices[i]->src = vertex->id;
			vertices[i]->toProcess = true;
		}
	}
}

vector<int> backtracePath(vector<DijkstraVertex*>& vertices, int src, int dst){
	vector<int> path;
	DijkstraVertex* vertex = vertices[dst];
	path.push_back(dst);
	while(vertex != vertices[src]){
		path.push_back(vertex->src);
		vertex = vertices[vertex->src];
	}
	return path;
}

DijkstraVertex* getMinVertex(vector<DijkstraVertex*> vertices){
	int minWeight = maxWeight;
	DijkstraVertex* minVertex = NULL;
	for(unsigned i=0;i<vertices.size();i++){
		DijkstraVertex* vertex = vertices[i];
		if(vertex->toProcess && vertex->weight < minWeight){
			minVertex = vertex;
			minWeight = minVertex->weight;
		}
	}
	minVertex->toProcess = false;
	return minVertex;
}

vector<int> getPath(vector<vector<int> >& adiacenceMatrix, int src, int dst){
	vector<DijkstraVertex*> vertices = prepareVertices(src, adiacenceMatrix.size());
    while(true){
    	DijkstraVertex* vertex = getMinVertex(vertices);
    	if (vertex->id == dst){
    		break;
    	}
    	relaxateVertex(vertex, adiacenceMatrix, vertices);
    }
    return backtracePath(vertices, src, dst);
}

int main(){
    vector<int> a;// = {0,1,3};
    a.push_back(0);
    a.push_back(1);
    a.push_back(3);
    vector<int> b;// = {1,0,1};
    b.push_back(1);
    b.push_back(0);
    b.push_back(1);
    vector<int> c;// = {3,1,0};
    c.push_back(3);
    c.push_back(1);
    c.push_back(0);
    vector<vector<int> > dane;// = {a,b,c};
    dane.push_back(a);
    dane.push_back(b);
    dane.push_back(c);
    vector<int> wynik = getPath(dane, 0, 2);
    for(unsigned int i=0;i<wynik.size();i++){
        cout<<wynik[i]<<" ";
    }
    return 0;
}

Dobra wszystko działa pięknie, dziękuję bardzo za pomoc;)

Mógłbyś dodać jeszcze do tego funkcję wyznaczająca odległość?

Odległość czego? Przecież to jest Dijkstra. Każdy wierzchołek ma informacje o odległości od źródła. To nic nie trzeba wyznaczać, bo już jest wyznaczone. To tak jakby prosić o funkcję wyznaczająca numer wierzchołka...