在链表图实现

Question

Dijkstra算法大问题，我有一个链表实现我的图中，两个顶点和边，并且正在成为Dijkstra算法的问题。正如我在上一个问题中所说的，我正在转换this code，它使用一个邻接矩阵来处理我的图形实现。

问题是，当我找到最小值时，我得到一个数组索引。如果图顶点存储在数组中，该索引将与顶点索引匹配。而对顶点的访问将是不变的。

我没有时间更改我的图形实现，但我确实有一个散列表，由唯一编号索引（但不是从0开始，它就像100090000），这是我的问题有。无论何时我需要，我使用模运算符来获得一个介于0和顶点总数之间的数字。

这对于当我需要一个数组索引从数字工作正常，但是当我需要的数量从数组索引（访问恒定的时间所计算出的最小距离顶点），没有这么多。

我试图寻找如何反模操作，如，100090000 MOD 18000 = 10000和10000 invmod 18000 = 10009万，但无法找到一个方法来做到这一点。

我的下一个选择是构建某种参考数组，其中，在上面的示例中，arr [10000] = 100090000.这将解决问题，但需要再次循环整个图形。

我对当前的图形实现有更好的/更简单的解决方案吗？

Answer 1

在你的阵列，而不是仅仅存储计（或任何你存储在那里），存储其中包含数以及顶点索引号的结构。