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