c++ - 图中的最短路径

Question

我的图表是通过以下方式实现的：

struct node{
    string ID;
    vector<string> neighbors;

}

struct graph{
    vector<string> nodes;
}

节点是节点的向量。每个节点都包含其 ID 和所有邻居（它指向的节点）ID 的向量

有没有办法可以应用 Dijkstra 算法或 Bellman-Ford 来找到两个节点之间的最短路径？找到重复循环？我该怎么做？

编辑：结构意外命名相同。

Answer 1

你没有提到边缘重量。

如果您没有负边权重，Dijkstra 算法就可以工作。

如果没有负循环，贝尔曼福特算法就可以工作。但是你也可以使用 Bellman-Ford 算法来检查你是否有负循环。

如果它是无权边图，则可以使用 BFS。