我用链表实现了我的图,用于顶点和边,这已成为 Dijkstra 算法的一个问题。正如我在上一个问题中所说,我正在转换使用邻接矩阵的代码来处理我的图形实现。
问题是当我找到最小值时,我得到一个数组索引。如果图形顶点存储在数组中,则该索引将与顶点索引匹配。并且对顶点的访问将是恒定的。
我没有时间更改我的图形实现,但我确实有一个哈希表,由一个唯一编号(但不是从 0 开始,就像 100090000)索引,这是我遇到的问题。每当我需要时,我都会使用模运算符来获得一个介于 0 和顶点总数之间的数字。
当我需要来自数字的数组索引时,这很好用,但是当我需要来自数组索引的数字(以在恒定时间内访问计算出的最小距离顶点)时,就不是那么多了。
我试图搜索如何反转模运算,例如 100090000 mod 18000 = 10000 和 10000 invmod 18000 = 100090000 但找不到方法。
我的下一个替代方法是构建某种参考数组,在上面的示例中,arr[10000] = 100090000。这将解决问题,但需要再循环一次整个图。
我当前的图形实现是否有更好/更简单的解决方案?