c - 寻找边数最少的最短路径(源和目的地之间)

Question

我正在尝试编写一个程序，查找图中两个顶点之间的最小长度路径，从这些路径中选择遍历最少边的路径之一。我使用了 Dijkstra 算法并进行了一些修改(如下)。

输出应该是:0->3->4，但我的程序却打印了0->4。为什么我得到错误的输出？

#include<stdio.h>
#include<string.h>
#define INFINITY 9999
#define n 5
#define s 0
#define d 4

void Dijkstra(int Graph[n][n], int _n,int _s, int _d);

int main()
{
    int Graph[n][n] = {
        {0, 6, 5, 1, INFINITY},
        {6, 0, 3, INFINITY, INFINITY},
        {5, 3, 0, 2, 5},
        {1, INFINITY, 2, 0, 6},
        {INFINITY, INFINITY, 5, 6, 0}
    };

    Dijkstra(Graph,n,s,d);
    getchar();
    return 0;
}

void Dijkstra(int Graph[n][n], int _n,int _s, int _d)
{
    int distance[n], parent[n], visited[n], edge[n]={0}, mindistance,
            nextnode= _s, i, j,temp[n][n], res[n];

    //parent[] stores the predecessor of each node
    //edge[] stores the number of edged of every vertex's shortest path

    for (i = 0; i < n; i++)       //create the temp matrix
        for (j = 0; j < n; j++)
            if (Graph[i][j] == INFINITY)
                temp[i][j] = INFINITY;
            else
                temp[i][j] = Graph[i][j];

    for(i=0;i<n;i++)
    {
        distance[i] = INFINITY;   //initialize distance
        parent[i] = _s;           //initialize parent
        visited[i] = 0;
        if (distance[i] > 0 && distance[i] < INFINITY)
            edge[i]++;
    }

    distance[_s] = 0;
    visited[_s] = 1;

    while (visited[_d] == 0)
    {
        //nextnode gives the node at minimum distance
        for (i = 0; i < n; i++)
        {
            mindistance = temp[_s][i] + distance[i];
            if (distance[i] < mindistance && !visited[i])
            {
                mindistance = distance[i];
                nextnode = i;
            }
        }

        //check if a better path exists through nextnode            
        visited[nextnode] = 1;

        if (nextnode != _d)
            for (i = 0; i < n; i++)
                if (!visited[i])
                {
                    if (mindistance + Graph[nextnode][i] < distance[i])
                    {
                        distance[i] = mindistance + Graph[nextnode][i];
                        parent[i] = nextnode;
                        edge[i] = edge[nextnode] + 1;
                    }

                    if (mindistance + Graph[nextnode][i] == distance[i])
                    {
                        if (edge[i] >= edge[nextnode] + 1)

                        {
                            parent[i] = nextnode;
                            edge[i] = edge[nextnode] + 1;
                        }
                    }
                }
    }

    //print the path 
    for (i = 0; i < n; i++)
        res[i] = 0;

    i = nextnode;

    while (i != _s)
    {
        res[i] = parent[i];
        i = parent[i];
    }

    printf("%d", _s);
    printf("->");
    for (i = 0; i < n; i++)
    {
        if (res[i] != 0)
        {
            printf("%d", res[i]);
            printf("->");
        }
    }
    printf("%d", _d);
}

Answer 1

在选择下一个要遍历的节点的循环中，您遇到了一些问题。显然设置不正确

            mindistance = Graph[_s][i] + distance[i];

在每次迭代中，因为您需要 mindistance 来跟踪跨迭代的最小观察距离。相反，在您应该设置的循环

        mindistance = INFINITY;

当我们查看此循环时，还请注意您在选择要遍历的下一个节点时忽略了边计数标准。您也需要在这里使用该标准，以确保找到满足您的标准的路径。

通过这些更正，您的程序可以为我生成预期的输出。

顺便说一句，请注意，这仍然是非常直接的 Dijkstra。诀窍是要认识到您正在实现二元距离测量。最重要的组成部分是路径长度(边权重之和)，但边数是破坏联系的次要组成部分。因此，实现看起来有点不同，但如果您将距离比较和设置分解为单独的函数，那么您将无法将其余部分与标准 Dijkstra(简单变体)区分开来。