c语言 - 未加权图的 Dijkstra 算法

Question

这个程序是关于在未加权图中找到最短路径。我在我的结构graph中int **weight.我必须找到从源顶点到任何其他顶点v的最小距离。这就像Dijkstra的未加权图一样。

我得到了几乎正确的输出，除了最后一个顶点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 emptyn");
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
...
}