Dijkstra'算法-顶点作为坐标

Question

我通过了 Dijkstra 的最短路径算法，在练习时我遇到了一个问题，其中顶点不是 单个数字 （比如 1,2,3...等等）但它是一对更具体地给出的 (x,y)coordinates。我从来没有做过这种类型的问题，我也没有见过them.Can请你帮我看看如何处理这类问题。热烈欢迎O(V^2)

Answer 1

使用哈希图将坐标映射到整数顶点。现在你有一个节点作为单个数字的图形。应用 dijkstra 算法。

时间复杂度：O(V) 用于转换为整数顶点。
O(V^2) 用于运行 dijkstra 算法。
因此 O(V^2) 总复杂度。

伪代码：

int cntr = 0; 
for(Edge e : graph){
    int from = e.from;
    int to= e.to;
    if(!map.contains(from)){
        map.put(from, cntr++);    
    }

    if(!map.contains(to)){
        map.put(to, cntr++);    
    }
}

Answer 2

每个顶点仍然会有一个 id（如果没有给出，你可以分配）。笛卡尔坐标只是顶点的附加属性，可用于计算相连顶点之间的距离。 (平方(delta_x^2 + delta_y^2))

Dijkstra'算法-顶点作为坐标

Dijkstra' algorithm- vertex as coordinate

c++

algorithm

dijkstra

shortest-path