c++ - Dijkstra'算法-顶点作为坐标

Question

我学习了Dijkstra for shortest path algorithm，在练习时我遇到了一个问题，其中顶点不是单个数字(比如 1,2,3。 ..等等)但它是一对更具体地给出的(x，y)坐标。我从来没有做过这种类型的问题，也没有见过它们。你能帮我看看如何吗解决这类问题的方法。O(V^2) 非常受欢迎

Answer 1

使用 HashMap 将坐标映射到整数顶点。现在你有一个节点作为单个数字的图形。应用 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++);    
    }
}