返回最低节点的名称

Question

首先，这是大学课程的一部分，因此虽然复制粘贴解决方案也可以，但我正在寻找更深入的知识。不过我明天还是要见我的主管。

现在进入正题。我正在为 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);

}

为了正确实施该算法，我在 class 图中创建了前导函数 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 函数总是出现在 return 节点 C 上，导致它被一遍又一遍地打印，所以它填满了控制台。到目前为止，我已经尝试使用 visual studio 2017 进行调试，但我对手表没有太大的了解。我还调整了中断的顺序，并尝试确保已访问的标志设置为 true。我不确定是否有任何操作优先级对此有影响。

提前致谢。

Answer 1

我认为您实施此方法的方式存在多个问题...但我认为导致您描述的问题的是此处的声明：

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

想想这是做什么的。假设您的第一个节点不是您要查找的节点，那么您调用最小距离并找到下一个最小节点。然后你打印它。然后你再次迭代 while 循环，发现 CurrentNode 不是你要找的那个，所以你再次调用 LeastDistance(StartNode)，这将 return完全相同的值。因此，您将继续打印显然是 c.

的相同结果

假设其他一切都正确，我想你想要：

CurrentNode = LeastDistance(CurrentNode);

返回最低节点的名称

Returning name of lowest node

c++

vector

dijkstra