Dijkstraコードを修正してパスを印刷

Question

このDijkstraコードを隣接リストを使用してグラフに追加しましたが、最小パスを表示するように変更するのに問題があります。どんな助け？私は、各頂点への奥行きと近さを計算するために、先祖のベクトルが必要です。

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

struct AdjListNode 
{ 
    int dest; 
    int weight; 
    struct AdjListNode* next; 
}; 

struct AdjList 
{ 
    struct AdjListNode *head; // pointer to head node of list 
}; 

struct Graph 
{ 
    int V; 
    struct AdjList* array; 
}; 

struct AdjListNode* newAdjListNode(int dest, int weight) 
{ 
    struct AdjListNode* newNode = 
      (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
    newNode->dest = dest; 
    newNode->weight = weight; 
    newNode->next = NULL; 
    return newNode; 
} 

struct Graph* createGraph(int V) 
{ 
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); 
    graph->V = V; 

    // Create an array of adjacency lists. Size of array will be V 
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

    // Initialize each adjacency list as empty by making head as NULL 
    for (int i = 0; i < V; ++i) 
     graph->array[i].head = NULL; 

    return graph; 
} 

void addEdge(struct Graph* graph, int src, int dest, int weight) 
{ 
    // Add an edge from src to dest. A new node is added to the adjacency 
    // list of src. The node is added at the begining 
    struct AdjListNode* newNode = newAdjListNode(dest, weight); 
    newNode->next = graph->array[src].head; 
    graph->array[src].head = newNode; 

    // Since graph is undirected, add an edge from dest to src also 
    newNode = newAdjListNode(src, weight); 
    newNode->next = graph->array[dest].head; 
    graph->array[dest].head = newNode; 
} 

struct MinHeapNode 
{ 
    int v; 
    int dist; 
}; 

struct MinHeap 
{ 
    int size;  // Number of heap nodes present currently 
    int capacity; // Capacity of min heap 
    int *pos;  // This is needed for decreaseKey() 
    struct MinHeapNode **array; 
}; 

struct MinHeapNode* newMinHeapNode(int v, int dist) 
{ 
    struct MinHeapNode* minHeapNode = 
      (struct MinHeapNode*) malloc(sizeof(struct MinHeapNode)); 
    minHeapNode->v = v; 
    minHeapNode->dist = dist; 
    return minHeapNode; 
} 

struct MinHeap* createMinHeap(int capacity) 
{ 
    struct MinHeap* minHeap = 
     (struct MinHeap*) malloc(sizeof(struct MinHeap)); 
    minHeap->pos = (int *)malloc(capacity * sizeof(int)); 
    minHeap->size = 0; 
    minHeap->capacity = capacity; 
    minHeap->array = 
     (struct MinHeapNode**) malloc(capacity * sizeof(struct MinHeapNode*)); 
    return minHeap; 
} 

void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) 
{ 
    struct MinHeapNode* t = *a; 
    *a = *b; 
    *b = t; 
} 

void minHeapify(struct MinHeap* minHeap, int idx) 
{ 
    int smallest, left, right; 
    smallest = idx; 
    left = 2 * idx + 1; 
    right = 2 * idx + 2; 

    if (left < minHeap->size && 
     minHeap->array[left]->dist < minHeap->array[smallest]->dist) 
     smallest = left; 

    if (right < minHeap->size && 
     minHeap->array[right]->dist < minHeap->array[smallest]->dist) 
     smallest = right; 

    if (smallest != idx) 
    { 
     MinHeapNode *smallestNode = minHeap->array[smallest]; 
     MinHeapNode *idxNode = minHeap->array[idx]; 

     minHeap->pos[smallestNode->v] = idx; 
     minHeap->pos[idxNode->v] = smallest; 

     swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); 

     minHeapify(minHeap, smallest); 
    } 
} 

int isEmpty(struct MinHeap* minHeap) 
{ 
    return minHeap->size == 0; 
} 

struct MinHeapNode* extractMin(struct MinHeap* minHeap) 
{ 
    if (isEmpty(minHeap)) 
     return NULL; 

    struct MinHeapNode* root = minHeap->array[0]; 

    struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1]; 
    minHeap->array[0] = lastNode; 

    minHeap->pos[root->v] = minHeap->size-1; 
    minHeap->pos[lastNode->v] = 0; 

    --minHeap->size; 
    minHeapify(minHeap, 0); 

    return root; 
} 

void decreaseKey(struct MinHeap* minHeap, int v, int dist) 
{ 
    int i = minHeap->pos[v]; 

    minHeap->array[i]->dist = dist; 

    while (i && minHeap->array[i]->dist < minHeap->array[(i - 1)/2]->dist) 
    { 
     minHeap->pos[minHeap->array[i]->v] = (i-1)/2; 
     minHeap->pos[minHeap->array[(i-1)/2]->v] = i; 
     swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1)/2]); 

     i = (i - 1)/2; 
    } 
} 

bool isInMinHeap(struct MinHeap *minHeap, int v) 
{ 
    if (minHeap->pos[v] < minHeap->size) 
    return true; 
    return false; 
} 

void printArr(int dist[], int n) 
{ 
    printf("Vertex Distance from Source\n"); 
    for (int i = 0; i < n; ++i) 
     printf("%d \t\t %d\n", i, dist[i]); 
} 

void dijkstra(struct Graph* graph, int src) 
{ 
    int V = graph->V;// Get the number of vertices in graph 
    int dist[V];  // dist values used to pick minimum weight edge in cut 

    struct MinHeap* minHeap = createMinHeap(V); 

    for (int v = 0; v < V; ++v) 
    { 
     dist[v] = INT_MAX; 
     minHeap->array[v] = newMinHeapNode(v, dist[v]); 
     minHeap->pos[v] = v; 
    } 

    minHeap->array[src] = newMinHeapNode(src, dist[src]); 
    minHeap->pos[src] = src; 
    dist[src] = 0; 
    decreaseKey(minHeap, src, dist[src]); 

    minHeap->size = V; 

    while (!isEmpty(minHeap)) 
    { 
     struct MinHeapNode* minHeapNode = extractMin(minHeap); 
     int u = minHeapNode->v; // Store the extracted vertex number 

     struct AdjListNode* pCrawl = graph->array[u].head; 
     while (pCrawl != NULL) 
     { 
      int v = pCrawl->dest; 

      if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX && 
              pCrawl->weight + dist[u] < dist[v]) 
      { 
       dist[v] = dist[u] + pCrawl->weight; 
       decreaseKey(minHeap, v, dist[v]); 
      } 
      pCrawl = pCrawl->next; 
     } 
    } 
    printArr(dist, V); 
} 

Answer 1

parentポインタが前のノードを検出したことを示すようないくつかの追加情報を保存します。あなたがextractMin()操作を行うたび

struct MinHeapNode 
{ 
    int v; 
    int dist; 

    struct MinHeapNode *parent; 
} 

さて、あなたが得るアドレスは、あなたには、いくつかの一時的な変数に格納し、そしてあなたのノードであるので、例えば、場合minHeapNode->parent

struct MinHeapNode *prev = NULL; 
while (!isEmpty(minHeap)) 
    { 
     struct MinHeapNode* minHeapNode = extractMin(minHeap); 

     // Storing the previous node's address 
     minHeapNode->parent = prev; 
     prev = minHeapNode; 

     int u = minHeapNode->v; // Store the extracted vertex number 

に割り当てることができます 1 <- 2 <- 3 <- 4 <- 5

：このためには、 1 2 3 4 5

次に、あなたは次のような表現を取得することができます

whileループの最後に、逆方向に移動してデータを印刷することができます。以下のような関数が動作します。

void printPath (struct MinHeapNode *last) 
{ 
    while (last != NULL) 
    { 
     printf ("%d -> ", last->v); 

     last = last->parent; 
    } 

    printf ("NULL\n"); 
} 

独自の表示方法に機能を追加するか、この機能を自由に変更して表示することができます。さらなる疑問があればコメントしてください。