首先,这是一门大学课程的一部分,因此尽管可以使用复制粘贴解决方案,但我正在寻找更多的深度。无论如何,明天我仍然会见我的主管。
现在到问题了。我正在为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);