Алгротим Дейкстры для невзвешенных графов

Question

Эта программа предназначена для поиска кратчайшего пути в невзвешенном графике.Я взял int **weight в своей структуре graph.Я должен найти минимальное расстояние от исходной вершины до любой другой вершины v.Это как у Дейкстры для невзвешенных графов.

Я получаю почти правильный вывод, за исключением последней вершины 4, когда дело доходит до deque 4 и процесс завершается.

#include<stdio.h>  
#include<stdlib.h>
struct Queue{
    int rear;
    int front;
    int capacity;
    int* array;
};

struct adjlistnode{
    int dest;
    struct adjlistnode* next;
};

struct adjlist{
    struct adjlistnode* head;
};

struct graph{
    int V;
    int **weight;
    struct adjlist* array;
};

int visited[100];
int distance[100],path[100];

struct Queue* createqueue(int capacity){
    struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));
    queue->rear = -1;
    queue->front = -1;
    queue->capacity=capacity;
    queue->array=(int*)malloc(sizeof(int)*capacity);
    return queue;
}

int isempty(struct Queue* queue){
    return(queue->front==-1 && queue->rear==-1);
}

void enqueue(struct Queue* queue,int data){
    if(isempty(queue)){
        queue->rear=0;
        queue->front=0;
        queue->array[queue->rear]=data;
        printf("\n enqueing %d \n",queue->array[queue->rear]);
        return;
    }
    queue->rear=(queue->rear+1)%queue->capacity;
    queue->array[queue->rear]=data;
    printf("\n enqueuing %d \n",queue->array[queue->rear]);
}

int dequeue(struct Queue* queue){
    if(isempty(queue)){
        printf("\nreturning queue is empty\n");
        return -1;
    }
    if(queue->front==queue->rear){
        int temp=queue->front;
        queue->rear=-1;
        queue->front=-1;
        printf("\n front and rear are equal dequeing  %d \n",queue->array[temp]);
        return queue->array[temp];
    }
    else{
        int temp=queue->front;
        queue->front=(queue->front+1)%queue->capacity;
        printf("\ndequeuing %d \n",queue->array[temp]);
        return (queue->array[temp]);
    }
}

int isfront(struct Queue* queue){
    return(queue->array[queue->front]);
}

struct graph* creategraph(int v){
    struct graph* G=(struct graph*)malloc(sizeof(struct graph));
    G->V=v;
    G->array=(struct adjlist*)malloc(v*sizeof(struct adjlist));
    G->weight=malloc(v*sizeof(int*));
    for(int j=0;j<v;j++)
        G->weight[j]=malloc(sizeof(int)*v);
    for(int i=0;i<v;i++)
        G->array[i].head=NULL;
    return G;
}

struct adjlistnode* getnewnode(int dest){
    struct adjlistnode* newnode = malloc(sizeof(struct adjlistnode*));
    newnode->dest=dest;
    newnode->next=NULL;
    return newnode;
}

void addedge(struct graph* G,int src ,int dst){
    struct adjlistnode* temp = getnewnode(dst);
    temp->next = G->array[src].head;
    G->array[src].head=temp;

    printf(" \n enter the weight \n ");
    int n;
    scanf("%d",&n);
    G->weight[src][dst]=n;
    G->weight[dst][src]=n;
}

void shpu(struct graph* G,struct Queue* queue,int s){
    int v,w;
    enqueue(queue,s);
    distance[s]=0;
    while(!isempty(queue)){
        v=dequeue(queue);
        struct adjlistnode* temp = G->array[v].head;
        while(temp!=NULL){
            if(distance[temp->dest]==-1){
                printf("\ntemp->dest = %d \n",temp->dest);
                printf("\n v is %d \n",v);
                distance[temp->dest]=distance[v] + 1;
                path[temp->dest]=v;
                enqueue(queue,temp->dest);
            }
            temp=temp->next;
        }
    }
}

int main(){
    struct graph* G = creategraph(5);
    struct Queue* queue = createqueue(100);
    addedge(G,0,1);
    addedge(G,1,2);
    addedge(G,3,4);
    addedge(G,2,3);
    addedge(G,4,1);
    for(int i=0;i < 100;i++){
        distance[i]=-1;
    }

    shpu(G,queue,1);
    for(int i=0;i<100;i++){
        printf(" %d ",path[i]);
    }
}

Answer 1

Как правило, в Dijkstra, ваша очередь должна содержать информацию о краях в порядке убывания весов.Но так как весовые коэффициенты 0 в вашем случае, вы можете отказаться от всего, что вы делаете (BFS).

Вы ошиблись в процедуре addHead().В первых трех строках вы добавляете ненаправленный край от src до dst, но что случилось с обратным?Так что просто добавьте dst к src, и все будет хорошо.

void addedge(struct graph* G,int src ,int dst){
    struct adjlistnode* temp = getnewnode(dst);
    temp->next = G->array[src].head;
    G->array[src].head=temp;            // Add src to dst
    struct adjlistnode* temp2 = getnewnode(src);
    temp2->next = G->array[dst].head;
    G->array[dst].head = temp2;        // Add dst to src

    ...
}