c++ - 如何使用二维 vector 表示 Dijkstra 算法中的边权重

Question

我希望能够通过这样做来访问边的权重:

int edgeWeightOfTwoVertexes = 权重[vertexA][vertexB];

vertexA 和 vertexB 是我的 vertex 类中的对象。那么我该如何初始化 2D vector 才能让它发挥作用呢？

我从未见过通过非整数值访问 vector/数组元素，所以我想知道这样的事情是否可行。如果没有，还有什么其他建议可以存储和快速访问边缘权重？

Answer 1

您可以将边表示为

std::pair<int, int>  // first = source, second = destination

那么你的边权重可以是

std::map<std::pair<int, int>, int> weights;

关键是你的优势(由开始和结束节点指定)，值(value)是成本。所以你可以说

int edgeWeightOfTwoVertexes = weights[{vertexA, vertexB}];

否则如果你想坚持使用 2D vector ，你会有一个

std::vector<std::vector<int>> weights;

然后你可以访问它

int edgeWeightOfTwoVertexes = weights[vertexA][vertexB];

但要知道，通常这些图最终非常稀疏，这不是对内存的有效利用。

编辑
如果您的顶点是某个 Vertex 类的实例，我会给每个 Vertex 一个从 0 到顶点数的 id，然后您可以用这些来索引

weights[vertexA.id][vertexB.id]