Dijkstra算法C语言代码路径显示缺失目标节点问题咨询

Hey there! I see the issue with your Dijkstra's implementation—when outputting the shortest path, the target node is missing from the printed result. Let's walk through why this happens and fix it properly.

What's Going Wrong? #

Looking at your original path-printing code, you do have a line that prints the target node (printf("\nPath=%d",i);), but there are two potential issues that could be causing it to not work as expected:

1. The loop condition while(count < n-1) means you're not processing all nodes (you're missing one node when n > 2, which could lead to incorrect pred values for some nodes).
2. Directly printing the path in a do-while loop can lead to confusion with loop termination, especially if the pred array isn't fully populated.

Fixed Implementation #

Here's the corrected code with robust path printing and the loop condition fixed:

#include <stdio.h>
#define INFINITY 9999
#define MAX 10

void dijkstra(int G[MAX][MAX], int n, int startnode);

int main() {
    int G[MAX][MAX], i, j, n, u;
    printf("Enter no. of vertices: ");
    scanf("%d", &n);
    
    printf("\nEnter the adjacency matrix (enter 0 for no edge):\n");
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            scanf("%d", &G[i][j]);
        }
    }
    
    printf("\nEnter the starting node: ");
    scanf("%d", &u);
    
    dijkstra(G, n, u);
    return 0;
}

void dijkstra(int G[MAX][MAX], int n, int startnode) {
    int cost[MAX][MAX], distance[MAX], pred[MAX];
    int visited[MAX], count, mindistance, nextnode, i, j;
    
    // Create cost matrix: replace 0 (no edge) with infinity
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            if(G[i][j] == 0)
                cost[i][j] = INFINITY;
            else
                cost[i][j] = G[i][j];
        }
    }
    
    // Initialize predecessor, distance, and visited arrays
    for(i = 0; i < n; i++) {
        distance[i] = cost[startnode][i];
        pred[i] = startnode;
        visited[i] = 0;
    }
    distance[startnode] = 0;
    visited[startnode] = 1;
    count = 1;
    
    // Fix: Process all nodes (loop until count < n instead of n-1)
    while(count < n) {
        mindistance = INFINITY;
        
        // Find unvisited node with minimum distance from start
        for(i = 0; i < n; i++) {
            if(distance[i] < mindistance && !visited[i]) {
                mindistance = distance[i];
                nextnode = i;
            }
        }
        
        // Mark node as visited and update distances for neighbors
        visited[nextnode] = 1;
        for(i = 0; i < n; i++) {
            if(!visited[i] && mindistance + cost[nextnode][i] < distance[i]) {
                distance[i] = mindistance + cost[nextnode][i];
                pred[i] = nextnode;
            }
        }
        count++;
    }
    
    // Print results for each node
    for(i = 0; i < n; i++) {
        if(i != startnode) {
            printf("\nDistance of node %d = %d", i, distance[i]);
            printf("\nPath: ");
            
            // Temporary array to store path nodes (target -> start)
            int path[MAX], path_len = 0;
            j = i;
            
            // Traverse from target back to start node
            while(j != startnode) {
                path[path_len++] = j;
                j = pred[j];
            }
            path[path_len++] = startnode;
            
            // Print path in target <- predecessor <- ... <- start order
            printf("%d", path[0]);
            for(int k = 1; k < path_len; k++) {
                printf(" <- %d", path[k]);
            }
        }
    }
}

Key Changes Made #

1. Loop Condition Fix: Changed while(count < n-1) to while(count < n) to ensure every node is processed. Your original code was skipping one node, which could lead to incorrect predecessor values.
2. Robust Path Printing: Instead of printing directly in a loop, we first collect all path nodes in an array by traversing from the target back to the start. Then we print the array in order to get the clean target <- predecessor <- ... <- start format you need.
3. Readability: Added comments and spacing to make the code easier to follow, plus clarified input instructions.

Example Output #

For your test case (start node 0 to target node 5), you'll now see the correct path:

Distance of node 5 = [calculated shortest distance]
Path: 5 <- 3 <- 4 <- 0

内容的提问来源于stack exchange，提问作者Sadia Parveen