C中的Dijkstra路径查找器

Question

我正在学习Dijkstra algorithm and I am testing out this code from GeeksforGeeks。我希望程序也打印 2 个节点之间最短距离的路径。

我定义：

int parent[V]

作为一个全局变量来存储节点，这些节点将给我尽可能短的路径。并且：

int end_point = 5;

设置结束节点为5

// A C program for Dijkstra's single source shortest path algorithm. 
// The program is for adjacency matrix representation of the graph 

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


// Number of vertices in the graph 
#define V 9 
  
// Define shortest path array
int parent[V];
int end_node = 5;

// A utility function to find the vertex with minimum distance value, from 
// the set of vertices not yet included in shortest path tree 
int minDistance(int dist[], bool sptSet[]) 
{ 
    // Initialize min value 
    int min = INT_MAX, min_index; 
  
    for (int v = 0; v < V; v++) 
        if (sptSet[v] == false && dist[v] <= min) 
            min = dist[v], min_index = v; 
  
    return min_index; 
} 
  
// A utility function to print the constructed distance array 
void printSolution(int dist[]) 
{ 
    printf("Vertex \t\t Distance from Source\n"); 
    for (int i = 0; i < V; i++) 
        printf("%d \t\t %d\n", i, dist[i]); 
} 

void printparent()
{
    for (int i = 0; i < end_node; i++){
        if(parent[i]){
             printf("%d --> ", parent[i]);
        }
    }
}

// Function that implements Dijkstra's single source shortest path algorithm 
// for a graph represented using adjacency matrix representation 
void dijkstra(int graph[V][V], int src) 
{ 
    int dist[V]; // The output array.  dist[i] will hold the shortest 
    // distance from src to i 
  
    bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest 
    // path tree or shortest distance from src to i is finalized 
  
    // Initialize all distances as INFINITE and stpSet[] as false 
    for (int i = 0; i < V; i++) 
        dist[i] = INT_MAX, sptSet[i] = false; 
  
    // Distance of source vertex from itself is always 0 
    dist[src] = 0; 
    parent[src] = 0;
  
    // Find shortest path for all vertices 
    for (int count = 0; count < V - 1; count++) { 
        // Pick the minimum distance vertex from the set of vertices not 
        // yet processed. u is always equal to src in the first iteration. 
        int u = minDistance(dist, sptSet); 
  
        // Mark the picked vertex as processed 
        sptSet[u] = true; 
        
  
        // Update dist value of the adjacent vertices of the picked vertex. 
        for (int v = 0; v < V; v++) 
  
            // Update dist[v] only if is not in sptSet, there is an edge from 
            // u to v, and total weight of path from src to  v through u is 
            // smaller than current value of dist[v] 
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v]; 
                parent[v] = u;
            }
    } 
  
    // print the constructed distance array 
    printSolution(dist); 
} 
  
// driver program to test above function 
int main() 
{ 
    /* Let us create the example graph discussed above */
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
                        { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, 
                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, 
                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; 
  
    dijkstra(graph, 0); 
    printparent();
  
    return 0; 
}

程序打印出正确的0和5之间的最短距离，即11，但没有打印出正确的路线：

Vertex           Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14
1 --> 2 --> 5 -->

从0到5的正确最短路线应该是：

0 --> 7 --> 6 --> 5 -->

长度为 11。

我应该如何修正我的代码以打印正确的最短路径？

数组部分存储最短路径，代码如下：

int array[100];
int a;

void printparent(){
     n = end_node;
     while(n != 0){
          array[a] = n;
          printf("%s --> ", n);
          n = parent[n];
          a++;
     }
}

Answer 1

你的 printparent() 函数对我来说完全没有意义。

首先，考虑循环的迭代边界：

    for (int i = 0; i < end_node; i++){

仅考虑节点 0 到 end_node 的 parent 有何意义？最短路径可以很好地通过其他节点。

其次，考虑打印的条件：

        if(parent[i]){

parent 数组包含从 0 开始的顶点编号。该条件将始终跳过 parent 为节点 0 的节点，因此如果该路径包含，则无法打印正确的最短路径节点 0（和你一样）。

但是还要考虑打印 parent 的顺序，以及要打印的 parent 的选择。如果节点 N 在最短路径上，并且有 parent P，那么你想在打印 P 之后立即打印 N，但只有在偶然情况下才会这样如果您只是按索引顺序遍历 parent 数组，就会发生这种情况。并且没有理由期望这种方法能够可靠地忽略添加到最短路径树的节点，但不会出现在起始节点和结束节点之间的最短路径上。

您需要一种完全不同的方法来打印最短路径。打印反向路径其实更自然：

从打印结束节点开始；
在每个后续步骤中，打印 parent[n]，其中 n 是上一次迭代中打印的节点
到达源节点时停止，或者如果您不想将源节点作为参数传递，则在到达没有 parent

（当然，您确实需要一种不同于 parent[i] == 0 的方式来指定“没有 parent”。）

正向打印路径，需要先按照说明向后追踪，然后倒序打印结果。您可以通过将它们存储在一个数组中然后向后迭代它来做到这一点，或者通过递归地进行路径发现，在递归调用 returns.

之后打印每个节点

C中的Dijkstra路径查找器

Dijkstra path finder in C

c

algorithm

shortest-path

dijkstra