首先,这是一门大学课程的一部分,因此尽管可以使用复制粘贴解决方案,但我正在寻找更多的深度。无论如何,明天我仍然会见我的主管。

现在到问题了。我正在为5个链接的节点A-E实现Dijkstra的算法,这些节点的相关成本和链接存储在向量中;

struct Node
{
    char nodeLink;  //adjacent link
    int cost;       //cost of a link
};                  //to use in Dijkstra algorithm


class HeadNode
{
public:
    char Name;
    bool Visited;
    vector<Node> nodes;
    HeadNode(char x) { Name = x; Visited = false; }

};

class Graph
{
    char Start = 'A';
    char StartNode;
    char CurrentNode;
    char Destination = 'E';
    int TotalCost = 0;
    vector<HeadNode> hnode;
    vector<char> path;
    vector<int> weight;

public:
    Graph();
    void createHeadNode(char X);
    void createAdjMatrix();
    char LeastDistance(char node);
    void printAdjMatrix();
    void Dijkstra(char StartNode);
    char GetStartNode();
};



int main()
{
    Graph graph;
    graph.createHeadNode('A');
    graph.createHeadNode('B');
    graph.createHeadNode('C');
    graph.createHeadNode('D');
    graph.createHeadNode('E');

    graph.createAdjMatrix();
    //graph.printAdjMatrix();
    graph.Dijkstra(graph.GetStartNode());

    system("pause");
    return 0;
}

Graph::Graph()
{
}


void Graph::createHeadNode(char x)
{
    hnode.push_back(x);

}


为了正确实现该算法,我在类图中创建了一个前驱函数LeastDistance()。我也有一个获取起始节点的函数,但这在这里并不是特别重要。

char Graph::LeastDistance(char node)
{
    int smallest = 9999;
    char smallestNode;

    for (int i = 0; i < hnode.size(); i++)
    {
        for (int j = 0; j < hnode[i].nodes.size(); ++j)
        {
            if ((node == hnode[i].Name) && (hnode[i].nodes[j].cost <= smallest) && (hnode[i].Visited == false))
            {
                smallest = hnode[i].nodes[j].cost;
                smallestNode = hnode[i].nodes[j].nodeLink;
            }
            else
            {
                hnode[i].Visited = true;
                break;
            }
        }
    }
    TotalCost = TotalCost + smallest;
    return(smallestNode);
}

void Graph::Dijkstra(char StartNode)
{
    CurrentNode = StartNode;
    if (CurrentNode == Destination)
    {
        cout << "the start is the destination, therefore the cost will be 0." << endl;
    }
    else
    {
        while(true)
        {
            if (CurrentNode != Destination)
            {
                CurrentNode = LeastDistance(StartNode);
                cout << CurrentNode << "<-";
            }
            else if (CurrentNode == Destination)
            {
                cout << endl;
                cout << "The total cost of this path is:" << TotalCost;
                TotalCost = 0;//reset cost
                break;
            }
        }
    }

}


我的问题是LeastDistance功能总是出现在返回节点C的位置,导致它一遍又一遍地打印,因此它填满了控制台。到目前为止,我已经尝试使用Visual Studio 2017进行调试,但是我对这些表没有多大意义。我还调整了中断的顺序,并尝试确保将访问标志设置为true。我不确定操作的任何优先顺序是否会影响这一点。

提前致谢。

最佳答案

我认为实现此方法的方式存在多个问题...但是我认为,导致您描述的问题的是此处的语句:

if (CurrentNode != Destination)
{
    CurrentNode = LeastDistance(StartNode);
    cout << CurrentNode << "<-";
}


考虑一下这样做。假设您的第一个节点不是您要查找的节点,然后您调用最小距离并找到下一个最小节点。然后打印。然后,您再次遍历while循环,只是发现CurrentNode不是您要查找的那个,因此再次调用LeastDistance(StartNode),它将返回完全相同的值。因此,您将继续打印相同的结果,显然是c

假设其他所有内容都正确,我想您需要:

CurrentNode = LeastDistance(CurrentNode);

07-24 09:45
查看更多