c - C中的Dijkstra路径查找器

问题描述

我正在学习Dijkstra 算法，并且正在测试GeeksforGeeks中的这段代码。我希望程序也打印两个节点之间最短距离的路径。

我定义：

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++;
     }
}

标签： calgorithmshortest-pathdijkstra

解决方案

你的printparent()功能对我来说根本没有意义。

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

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

只考虑节点 0 到的父节点有什么意义end_node？最短路径很可能通过其他节点。

其次，考虑打印的条件：

        if(parent[i]){

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

但是，此外，请考虑您打印父母的顺序，以及您正在打印的父母的选择。如果 nodeN位于最短路径上，并且具有 parent P，那么您希望在 printN之后立即打印P，但如果您只是parent按索引顺序遍历数组，那只会碰巧发生。并且没有理由期望这种方法会可靠地忽略添加到最短路径树中的节点，但不会出现在起始节点和结束节点之间的最短路径上。

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

首先打印结束节点；
在每个后续步骤中， print ，在前一次迭代中打印的节点在parent[n]哪里n
到达源节点时停止，或者如果您不想将源节点作为参数传递，则在到达没有父节点时停止

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

要打印正向的路径，您需要首先按照描述向后追溯，然后以相反的顺序打印结果。您可以通过将它们存储在一个数组中然后对其进行反向迭代来做到这一点，或者通过递归地进行路径发现，在递归调用返回后打印每个节点。

c - C中的Dijkstra路径查找器

问题描述

解决方案

推荐阅读