最低节点的返回名称 [英] Returning name of lowest node

问题描述

首先，这是一门大学课程的一部分，因此尽管可以执行复制粘贴解决方案，但我正在寻找更多的深度。无论如何，明天我还是会见上司的。

First of all, this is part of a university course, so whilst a copy-paste solution would do, I'm looking for a bit more depth. I'll be seeing my supervisor tomorrow anyways though.

现在解决问题。我正在为5个链接节点AE实现Dijkstra的算法，这些链接节点的关联成本和链接存储在向量中；

Now onto the problem. I am implementing Dijkstra's algorithm for 5 linked nodes, A-E, which have their associated costs and links stored in a vector;

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（）。我也有一个获取起始节点的函数，但这在这里不是特别重要；

In order to properly implement the algorithm, I have created a precursor function, LeastDistance(), within the class graph. I also have a function to get the start node, but that isn't particularly important here;

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。我不确定操作的优先顺序是否会影响到此。

My problem is that the LeastDistance fucntion appears always to return node C, leading to it being printed over and over, so it fills the console. So far, I have tried to debug using visual studio 2017, but I cant make much sense out of the watches. I have also tweaked the order of the breaks around, and tried to make sure the visited flag is being set to true. whether any precedence of operations is affecting this I am not sure.

预先感谢。

推荐答案

我认为实现此方法的方式有多个问题...但是我认为，导致您描述的问题的是这里的语句：

I would contend that there are multiple problems with the way you implement this... but I think the one that's causing you the problem you describe is the statement right here:

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

请考虑这样做。假设您的第一个节点不是您要查找的节点，然后您调用最小距离并找到下一个最小节点。然后打印。然后，您再次在 while 循环中进行迭代，却发现 CurrentNode 不是您要查找的那个，因此您再次调用 LeastDistance（StartNode），这将返回完全相同的值。因此，您将继续打印相同的结果，显然是 c 。

Think about what this does. Let's say your first node isn't the one you're looking for, then you call least distance and find the next smallest node. Then you print it. Then you iterate on the while loop again only to find that CurrentNode isn't the one you're looking for, so you call LeastDistance(StartNode) again, which will return the exactly same value. Thus, you'll keep printing the same result which apparently is c.

假设其他所有内容都正确，我想你想要的

Assuming everything else is correct, I think you want:

CurrentNode = LeastDistance(CurrentNode);

这篇关于最低节点的返回名称的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！