Znowu mnie coś przerosło i walę do was o pomoc. W skrócie Dijkstra a dokładniej implementacja jego algorytmu za pomocą C. Wiem, że na wikipedi jest to rozpisane, ale męczę się już z tym kilka godzin i dalej nic nie mam. Czy mógł by mi ktoś napisać lub wytłumaczyć jak to napisać? Mam kwadratową macierz odległości(wag) o rozmiarze ilość wszystkich punktów
gdzie matrix[i][j] to odległość z punktu i do j. Tam gdzie nie ma połączeń jest max wartość int a matrix[i][i]=0. Z tego co rozumiem to muszę zrobić dwie macieże d[x]-odległość do początku, p[x]-poprzedni punkt. Tylko jak je wypełnić? Z góry dziękuję za każdą pomoc.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
struct city {
char citi[15];
struct city *next;
}*start_c=NULL;
struct data {
int dist;
char citi_1[15];
char citi_2[15];
struct data *next;
}*start_d=NULL;
struct search {
char begin[15];
char stop[15];
struct search *next;
}*start_s=NULL;
struct data *fill_list_data(FILE *f1)
{
struct data *new_data,*current;
int distance;
int i=0;
char city1[15];
char city2[15];
while(!feof(f1))
{
fscanf(f1," %s %s %d",city1,city2,&distance);
new_data=(struct data *)malloc(sizeof(struct data));
strcpy(new_data->citi_1, city1);
strcpy(new_data->citi_2, city2);
new_data->dist=distance;
new_data->next=NULL;
if(start_d == NULL)
{
start_d = new_data;
current = new_data;
}
else
{
current->next = new_data;
current = new_data;
}
}
}
struct search *fill_list_search(FILE *f2)
{
struct search *new_data,*current;
int distance;
char city1[15];
char city2[15];
while(!feof(f2))
{
fscanf(f2," %s %s",city1,city2);
new_data=(struct search *)malloc(sizeof(struct search));
strcpy(new_data->begin, city1);
strcpy(new_data->stop, city2);
new_data->next=NULL;
if(start_s == NULL)
{
start_s = new_data;
current = new_data;
}
else
{
current->next = new_data;
current = new_data;
}
}
return start_d;
}
void help() /*function printing instructions in case of errors*/
{
printf("========================================================\n");
printf(" Instruction\n");
printf(" The program should run from console with following\n");
printf("parameters: program.exe -d input1.txt -t input2.txt -o output.txt.\n");
printf("========================================================\n");
}
void display()
{
struct data *new_data;
struct search *new_search;
new_data=start_d;
struct city *new_city;
while(new_data!=NULL)
{
printf("%s--->",new_data->citi_1);
printf("%s ",new_data->citi_2);
printf("%d\n",new_data->dist);
new_data=new_data->next;
}
printf("NULL\n");
new_search=start_s;
while(new_search!=NULL)
{
printf("%s--->",new_search->begin);
printf("%s\n",new_search->stop);
new_search=new_search->next;
}
printf("NULL\n");
new_city=start_c;
while(new_city!=NULL)
{
printf("%s\n",new_city->citi);
new_city=new_city->next;
}
printf("NULL\n");
}
int city_list()
{
int i=0;
bool exist=0;
struct city *new_data,*current_check, *current;
struct data *current_1 = start_d;
bool first=0;
bool one_more=1;
while(current_1->next!=NULL)
{
if(first)
{
while(current_check->next!=NULL || one_more)
{
if(strcmp(current_1->citi_1, current_check->citi)==0)
{
exist=1;
break;
}
if(current_check->next==NULL)
{
one_more=0;
}
else
{
current_check=current_check->next;
}
}
}
if(!exist)
{
i++;
first =1;
new_data=(struct city *)malloc(sizeof(struct city));
strcpy(new_data->citi, current_1->citi_1);
new_data->next=NULL;
if(start_c == NULL)
{
start_c = new_data;
current = new_data;
}
else
{
current->next = new_data;
current = new_data;
}
}
current_check=start_c;
exist=0;
one_more=1;
current_1=current_1->next;
}
current_1=start_d;
exist=0;
while(current_1->next!=NULL)
{
while(current_check->next!=NULL || one_more)
{
if(strcmp(current_1->citi_2, current_check->citi)==0)
{
exist=1;
break;
}
if(current_check->next==NULL)
{
one_more=0;
}
else
{
current_check=current_check->next;
}
}
if(!exist)
{
i++;
first =1;
new_data=(struct city *)malloc(sizeof(struct city));
strcpy(new_data->citi, current_1->citi_2);
new_data->next=NULL;
if(start_c == NULL)
{
start_c = new_data;
current = new_data;
}
else
{
current->next = new_data;
current = new_data;
}
}
one_more=1;
exist=0;
current_check=start_c;
current_1=current_1->next;
}
return i;
}
int fill_matrix(int j, int k)
{
struct city *current=start_c;
int x=0;
int y=0;
char adress_1[15];
char adress_2[15];
bool one_more=1;
if(j==k)
{
return 0;
}
else
{
while(x!=j)
{
current=current->next;
x++;
}
strcpy(adress_1, current->citi);
current=start_c;
while(y!=k)
{
current=current->next;
y++;
}
strcpy(adress_2, current->citi);
struct data *current_1 = start_d;
while(current_1->next!=NULL || one_more)
{
if(strcmp(current_1->citi_1, adress_1)==0 && strcmp(current_1->citi_2, adress_2)==0)
{
return current_1->dist;
}
if(current_1->next==NULL)
{
one_more=0;
}
else
{
current_1=current_1->next;
}
}
return 2147483647;
}
}
void find_route(int matrix[15][15], int x)
{
int j=0, k=0, r=0;
struct search *current=start_s;
struct city *current_1=start_c;
bool one_more=1;
int d[x];
int p[x];
while(r<x)
{
d[r]=2147483647;
p[r]=-1;
r++;
}
while(current->next!=NULL || one_more)
{
while(current_1->next!=NULL || one_more)
{
if(strcmp(current->begin, current_1->citi)==0)
{
break;
}
if(current_1->next==NULL)
{
one_more=0;
}
else
{
current_1=current_1->next;
}
j++;
}
current_1=start_c;
one_more=1;
while(current_1->next!=NULL || one_more)
{
if(strcmp(current->stop, current_1->citi)==0)
{
break;
}
if(current_1->next==NULL)
{
one_more=0;
}
else
{
current_1=current_1->next;
}
k++;
}
if(j==x || k==x)
{
print_error(current->begin, current->stop);
}
else
{
//Brakująca Funkcja
}
j=0;
k=0;
one_more=1;
if(current->next==NULL)
{
one_more=0;
}
else
{
current=current->next;
}
}
}
void print_error(char start[15], char stop[15])
{
printf("trasa: %s --> %s\n", start, stop);
printf(" TRASA NIEMOZLIWA DO WYLICZENIA\n");
}
int main(int argc, char** argv)
{
int x;
int i;
int j=0;
int k=0;
FILE* f1;
FILE* f2;
FILE* f3;
for (i = 0; i < argc; i++) /*loop opening proper arguments*/
{
if (strcmp(argv[i], "-d") == 0)
{
f1 = fopen(argv[i + 1], "r");
}
if (strcmp(argv[i], "-t") == 0)
{
f2 = fopen(argv[i + 1], "r");
}
if (strcmp(argv[i], "-o") == 0)
{
f3 = fopen(argv[i + 1], "w");
}
if (strcmp(argv[i], "-h") == 0)
{
help();
}
}
if (f1 == NULL || f2 == NULL || f3 == NULL)
{
help();
return;
}
fill_list_data(f1);
fill_list_search(f2);
x=city_list();
int matrix[x][x];
while(j<x)
{
while(k<x)
{
matrix[j][k]=fill_matrix(j, k);
printf("%d\t", matrix[j][k]);
k++;
}
printf("\n");
k=0;
j++;
}
find_route(matrix, x);
printf("%d\n", x);
display();
fclose(f1);
fclose(f2);
fclose(f3);
return 0;
}
Cały kod jakby ktoś chciał popatrzeć jak zarzynam piękny język C.