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

Question

我正在用c++编程Djikstra的算法，我正在从源节点到结束节点的正确距离，但我在回溯以前访问的节点时遇到了麻烦。它给了我正确的答案，但不是正确的答案。此外，我注意到不同的输入数据1作为开始节点和16作为完成节点，我的算法使用的路径是不允许的(它从1 -> 10 -> 8当8不允许)，但这可能只是我得到路径回溯错误。

http://pastebin。ca/3188762 -输入数据(第一个=最大节点，然后是节点(节点num, 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的数字。然后使用顶点数作为数组的索引。

修改代码，要么始终使用顶点数，要么始终使用数组索引。