Witam!
Proszę o pomoc w usprawnieniu kodu, tak aby program znalazł najszybszą drogę z pierwszego wierzchołka do każdego innego. Jestem początkująca i nie do końca wiem jak to zrobić :)
Kod źródłowy:
#include <stdio.h>
#include <iostream>
#define n 8
#define INF 9999999
using namespace std;
int W[n][n]={ // Macierz sąsiedztwa opisująca graf
{0,5,0,0,10,0,11,0},
{0,0,1,0,0,0,0,0},
{0,0,0,0,1,1,0,0},
{0,0,0,0,1,0,0,0},
{3,2,0,0,0,0,0,0},
{0,0,0,0,0,0,0,2},
{0,0,0,2,0,0,0,0},
{0,0,5,0,7,0,1,0}};
int Q[n]={1,1,1,1,1,1,1,1}; // Zbiór wuierzchołków do przetworzenia
int D[n]={INF,INF,INF,INF,INF,INF,INF,INF}; // Tablica odległości od s
int P[n]={-1,-1,-1,-1,-1,-1,-1,-1}; // Tabela poprzedników
void Dijkstra(int s){
int u,v; // Obsługiwane wierzchołki
int Dmin;
D[s]=0;
do{
Dmin=INF;
for(v=0;v<n;++v) // Szukamy takiego wierzchołka, który jest w Q
if(Q[v] && D[v]<Dmin){ // i jednocześnie ma najmniejszą wartość w D
u=v; // Znaleziony odpowiedni wierzchołek
Dmin=D[u]; // i jego najmniejsza odległość od s
}
if(Dmin==INF) break; // Jeżeli Dmin jest róna INF, to znaczy że Q jest puste
for(v=0;v<n;v++) // Przeglądamy sąsiadów wierzchołka u
if(u!=v && D[v]>W[u][v]+D[u]){ // Czy przypadkiem droga do v przez u nie jest krótsza niż wcześniej znaleziona?
D[v]=W[u][v]+D[u]; // Jeśli tak, to zapamiętujemy ten fakt (krótszą odległość)
P[v]=u; // i przez który wierzchołek jest krócej
}
}
while(1);
}
int main(){//zamieniałam void na int
int i,j;
cout<<"Nasz graf:\n";
for(i=0;i<n;++i){
for(j=0;j<n;j++) cout<<W[i][j]<<'\t';
cout<<endl;
}
Dijkstra(0);
cout<<"D = [";
for(i=0;i<n;i++) cout<<D[i]<<'\t'<<endl;
cout<<"]\nP = [";
for(i=0;i<n;i++) cout<<P[i]<<'\t'<<endl;
cout<<"]\n\n";
getchar();
return 0; //funkcja int zwraca wartośc 0
}
Shalom