(C++) Dijkstra 算法回溯问题

Question

我正在用 C++ 编写 Djikstra 算法，我得到了从源节点到结束节点的正确距离，但我无法回溯之前访问过的节点。它给了我某种正确答案，但不是正确答案。我还注意到，不同的输入数据 1 作为起始节点，16 作为结束节点，我的算法正在使用不允许的路径（当 8 不允许时，它从 1 -> 10 -> 8）但是可能只是我的路径回溯错误。

http://pastebin.ca/3188762 - 输入数据（第一个 = 最大节点，然后是节点（节点数，x，y），然后是最大边，然后是所有边，最后一行是开始和结束节点）

http://textuploader.com/awp89 - 在控制台中输出

代码：

#include<iostream>
#include<fstream>

using namespace std;

struct Node
{
    int nodeNum;
    double x, y;
};

void dji(double map[50][50],int startNode,int endNode,int maxNodes);

int main()
{
    int tempA, tempB, maxNodes, maxEdges, startNode, endNode;
    double tempD;
    double map[50][50];

    ifstream fin;
    fin.open("ass03.txt");
    if(fin.good())
    {
        fin >> maxNodes;

        Node allNodes[maxNodes];
        for(int i = 0; i < maxNodes; i++)
        {
            for(int k = 0; k < maxNodes; k++)
            {
                map[i][k] = -1;
            }
            map[i][i] = 0;
        }

        for(int i = 0; i < maxNodes; i++)
        {
            fin >> allNodes[i].nodeNum >> allNodes[i].x >> allNodes[i].y;
        }
        fin >> maxEdges;

        for(int i = 0; i < maxEdges; i++)
        {
            fin >> tempA >> tempB >> tempD;
            map[tempA-1][tempB-1] = tempD;
            map[tempB-1][tempA-1] = tempD;
        }

        fin >> startNode >> endNode;


        cout << "\t";

        for(int i = 0; i < maxNodes; i++)
        {
            cout << i+1 << "\t";
        }
        cout << endl;
        for(int i = 0; i < maxNodes; i++)
        {
            cout << i+1 << "\t";
            for(int k = 0; k < maxNodes; k++)
            {
                cout << map[i][k] << "\t";
            }
            cout << endl;
        }


        dji(map, startNode-1, endNode-1, maxNodes);

    }
    else
    {
        cout << "Incorrect filename" << endl;
    }


    return 0;
}




 void dji(double map[50][50], int startNode,int endNode,int maxNodes)
{
    int Intersections[maxNodes], path[maxNodes], temp; // equate for actual endNode
    double Distances[maxNodes];

    for(int a = 0; a < maxNodes; a++)
    {
        Intersections[a] = a;
        Distances[a] = map[startNode][a];

        if(map[startNode][a] != -1)
        {
            path[a] = startNode;
        }
        else
        {
            path[a] = -1;
        }
    }
    Intersections[startNode] = -1;
    Distances[startNode] = 0;

    double minValue = 99999;
    int minNode = 0;

    for(int l = 0; l < maxNodes; l++)//loop max amount of times to avoid having to function loop (disconsider l = startNode)?
    {
        for (int i = 0; i < maxNodes; i++)
        {
                if(Intersections[i] == -1)
                {
                    continue;
                }

                if(Distances[i] > 0 && Distances[i] < minValue)
                {
                minValue = Distances[i];
                minNode = i;
                }
        }


        if(Intersections[minNode] == endNode)
        {
            temp = l;
        }

        Intersections[minNode] = -1;

        cout << " --- Used Node - " << minNode+1 << endl;

        for(int i = 0; i < maxNodes; i++)
        {
            cout << Intersections[i] << " ";

        }
        cout << endl;

        for(int i = 0; i < maxNodes; i++) 
        {
            if(map[minNode][i] < 0)
            {
                continue;
            }

            if(Distances[i] < 0) 
            {
                Distances[i] = minValue + map[minNode][i];
                path[i] = minNode;
                continue;
            }

            if((Distances[minNode] + map[minNode][i]) < Distances[i]) 
            {
                Distances[i] = minValue + map[minNode][i];
                path[i] = minNode;
            }
        }

        minValue = 99999;
    }

    for(int i = 0; i < maxNodes; i++)
    {
        cout << "Node:"  << i+1 << " - PATH= " << path[i] << "     distance = " << Distances[i]  << endl;
    }

    cout << "Additional nodes used: " << temp << endl;

    temp = path[endNode];
    for(int i = 0; i < 4; i++)
    {
        cout << temp << " ";
        temp = path[temp];
    }

    /*temp = path[endNode];

    int temp2 = path[endNode];

    for(int i = 0; i < maxNodes; i++)
    {
        if(i == 0)
        {
            cout << endNode << " ";
            cout << temp << " ";
        }
        if(i%2 == 0)
        {
            if(temp != endNode)
            {
                temp = path[temp2];
                cout << temp << " ";
            }
            else
            {
                cout << temp << " ";
                i = maxNodes;
            }
        }
        else
        {
            if(temp2 != endNode)
            {
                temp2 = path[temp]-1;
                cout << temp2 << " ";
            }
            else
            {
                cout << temp2 << " ";
                i = maxNodes;
            }
        }
    }*/

    //cout << "PATH = " << endNode << " < - " << path[endNode] << " < - " << path[path[endNode]-1] << " < - " << path[path[path[endNode]-1]-1] <<  endl;

    //cout << "TEST" << path[4] << " " << path[8] << " " << path[16] << " " << endl;
}

感谢您的帮助

Answer 1

问题是您混合使用了基于零的索引和基于一的索引。您的顶点编号为 1-20，这些数字最终出现在您的 path 数组中，有效索引为 0-19。然后使用顶点编号作为数组的索引。

更改您的代码以始终使用顶点编号或始终使用数组索引。

(C++) Dijkstra 算法回溯问题

(C++) Dijkstra's Algorithm Backtracking issues

c++

algorithm

backtracking

shortest-path

output