Dijkstra-implementacja w c

0

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.

0

Uprzedzałem, przeanalizuj strukturę którą zaproponowałem, przerób dane na jej wzór, wtedy działająca całość będzie miała max 25% pojemności tego.
Wg mnie to nadaje się wyłącznie do kosza.
Z tym że jak się uprzesz to może być dobry moment na nauczenia się debugera.

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