Алгоритм Дейкстры

[Kharass]

Всем привет! Не могу разобраться, почему не не правильно работает алгоритм (пробовал на маленьких тестах - все ок, на больших неправильный ответ)

#include <stdio.h>
#include <stdlib.h>

struct list
{
    int vertex;
    long long dst;
    int check;
    struct list *next;
};

struct Queue
{
    struct list *head,*tail;
};

struct q_unit
{
    int vertex;
};

struct list *create_unit(int vrt,long long path_lenght)
{
    struct list *p = (struct list *) malloc (sizeof(struct list));
    p->dst = path_lenght;
    p->vertex = vrt;
    p->next = NULL;
    p->check = 0;
    return p;
}

void insert_list (struct list **A,int i,int vrt,long long path_lenght)
{
    struct list *p = create_unit(vrt,path_lenght);
    if (A[i]==NULL) A[i] = p;
    else
    {
        struct list *temp = A[i];
        while (temp->next) temp = temp->next;
        temp->next = p;
    }
}

void print_list (struct list *p)
{
    while (p)
    {
        printf("vrt=%d, dst=%lld\n",p->vertex,p->dst);
        p = p->next;
    }
}

void ins_queue (struct Queue *Q,struct list *p)
{
    struct list *q = create_unit(p->vertex,p->dst);
    if (Q->head==NULL)
    {
        Q->head = q;
        Q->head->next=Q->tail;
        Q->tail = q;
        Q->tail->next = NULL;
    }
    else
    {
        Q->tail->next = q;
        Q->tail = q;
    }
}

void print_Queue (struct Queue Q,struct list **A)
{
    struct list *p = Q.head;
    printf("Printing queue: ");
    while (p)
    {
        printf("%d ",p->vertex);
        p = p->next;
    }
    p = Q.head;
    printf("\n");
    while (p)
    {
        printf("%lld ",A[p->vertex-1]->dst);
        p = p->next;
    }
    printf("\n");
}

struct list *choose_pivot (struct Queue *Q,struct list **A)
{
    long long min = 1000001;
    struct list *pivot;
    struct list *t = Q->head;
    print_Queue(*Q,A);
    while (t) //выбираем наименьшую дистанцию
    {
        if (A[t->vertex-1]->dst<min)
        {
            pivot = t;
            min = t->dst;
        }
        t = t->next;
    }
    struct list *res = create_unit(pivot->vertex,pivot->dst);
    if (pivot==Q->head)
    {
        Q->head = Q->head->next;
        free(pivot);
    }
    else
    {
        t = Q->head;
        while (t->next!=pivot) t = t->next;
        if (pivot==Q->tail)
        {
            Q->tail = t;
            free(t->next);
            Q->tail->next=NULL;
        }
        else
        {
            t->next = pivot->next;
            free(pivot);
        }
    }
    return res;
}

void algorithm (struct list **A,struct Queue *Q)
{
    struct list *t = A[0]->next, *start;
    while (t)
    {
        ins_queue(Q,t);
        A[t->vertex-1]->dst = t->dst;
        t = t->next;
    }
    A[0]->check = 1;
    while (Q->head!=NULL)
    {
        //print_Queue(*Q);
        start = choose_pivot(Q,A); //вершина, на которую указывает голова стека
        start = A[start->vertex-1];
        printf("Working at %d:\n",start->vertex);
        t = start->next; //первая вершина, в которую есть путь из start
        if (start->check==0)
        {
            while (t)
            {
                printf("Now looking at %d\n",t->vertex);
                ins_queue(Q,t);
                printf("having in start %lld in t %lld and road %lld\n",start->dst,A[t->vertex-1]->dst,t->dst);
                if (start->dst + t->dst < A[t->vertex-1]->dst)
                    A[t->vertex-1]->dst = start->dst + t->dst;
                printf("having in start %lld in t %lld\n",start->dst,A[t->vertex-1]->dst);
                t = t->next;
            }
        start->check = 1; //просмотрели все пути и вершину
        }
    }
}

#define N 5

int main()
{
    FILE *fp;
    if (!(fp=fopen("ddata.txt","r")))
        printf("Can't open file!\n");
    static struct list *A[N];
    int i,ind;
    long long dst;
    char c;
    for (i=0;i<N;++i)
    {
        A[i]=NULL;
        fscanf(fp,"%d",&ind);
        dst = 1000000;
        insert_list(A,i,ind,dst);
        do
        {
            fscanf(fp,"%d,%lld%c",&ind,&dst,&c);
            insert_list(A,i,ind,dst);
        }
        while (c!='\n'&&c!='\r');
    }
    A[0]->dst=0;
    struct Queue Q;
    Q.head = Q.tail = NULL;
    algorithm(A,&Q);
    for (i=0;i<N;++i) printf("%lld ",A[i]->dst);
    fclose(fp);
    return 0;
}

[Bugrimov]

Поместите пожалуйста код в специальные теги #

[Kharass]

Исправился, прошу прощения за неудобство))

[Kharass]

Исправил немного код, стал правильно выводить очередь, но все еще неправильно работает на большом тесте.