Algorytm Dijkstry na tablicach - pomoc

0

Witam,
Chciałem napisac algorytm dijkstry na samych tablicach. Umęczyłem taki kod:

#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;


int main(int argc, char *argv[])
{
	
	fstream plik;
	int N,wierzcholek,warunek,istnieje,lp;
	int waga=500; // maxymalna waga wierzcholka
	
	plik.open("macierz.txt");
	plik >> N;
		
	int **macierz = new int *[N];
	int *odleglosci = new int[N];
	int *spr = new int[N];
	
	for(int i=0; i<N; i++) {
		macierz[i]=new int[N];
	}
	
	for(int i=0; i<N; i++) {	
		for(int j=0; j<N; j++)	
			plik >> macierz[i][j];
	}
	
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++)
			cout << macierz[i][j] << " ";
			cout << endl;
	}
		
	cout << "Wybierz wierzcholek startowy:\n";
	cin >> wierzcholek;
	
	for(int i=0; i<N; i++) {
			if(i==wierzcholek) odleglosci[i]=-1;
			else odleglosci[i]=0;
			}
		
	for(int i=0; i<N; i++) {
			if(i!=wierzcholek) { spr[i]=i; }
			else { spr[i]=-1; }
			}
	
	if(N>1) {
		warunek=1;
		
		while(warunek==1) {
		for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
						if(spr[i]==-1 && spr[j]!=-1) {
									  if((macierz[i][j]<waga) && (macierz[i][j]>0)) {
									  							 
									  							 lp=j;
									  							 waga=macierz[i][j];
																 }
										 }
					 }
			 }	
		
		
						odleglosci[lp]=waga;
						spr[lp]=-1;
						waga=500;
			 
			 
		for(int i=0; i<N; i++) {
				int ile=0;
				if(odleglosci[i]==0) ile++;
				if(ile==0) warunek=0;
				}
				

			
		}
	}
	
	
	cout << endl << endl;
	for(int i=0; i<N; i++) cout << spr[i] << ", ";
	
	cout << endl << endl;
	for(int i=0; i<N; i++) cout << odleglosci[i] << ", ";
	
	system("pause");
	return 0;
}

Przykladowy plik macierz.txt wyglada tak:

4
0 10 50 2
10 0 16 8
50 16 0 0
2 8 0 0

Wiem ze nie licze odleglosci, na razie chcialbym obliczyc tylko poszczegolne wagi pomiedzy wezlami.
Jesli za wierzcholek poczatkowy przyjme 0, to chciałbym aby tablice zmienialy sie w nastepujacy sposob:

Krok 0:
odleglosci: -1,0,0,0
spr: -1,1,2,3

Krok 1:
odleglosci: -1,0,0,2
spr: -1,1,2,-1

Krok 2:
odleglosci: -1,8,0,2
spr: -1,-1,2,-1

Krok 3:
odleglosci: -1,8,16,2
spr: -1,-1,-1,-1

Niestety petla zatrzymuje mi sie po kroku nr 1. Dlaczego? Co robie nie tak?
ps. wiem ze kod zagmatwany ale bede to poprawial jesli tylko "zaskoczy"

Prosze o pomoc

0

To weź w debugerze odpal i sprawdzaj gdzie się nie zgadza.

1 użytkowników online, w tym zalogowanych: 0, gości: 1