如何使用二维向量表示 Dijkstra 算法中的边权重

Question

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

int edgeWeightOfTwoVertexes = weights[vertexA][vertexB];

vertexA 和 vertexB 是我的 vertex class 中的对象。那么我该如何初始化 2D 向量才能让它工作呢？

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

Answer 1

您可以将边表示为

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

那么你的边权重可以是

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

键是你的边（由开始和结束节点指定），值是成本。所以你可以说

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

否则，如果你想坚持使用 2D 矢量，你会得到

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

然后你就可以访问那个了

int edgeWeightOfTwoVertexes = weights[vertexA][vertexB];

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

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

weights[vertexA.id][vertexB.id]