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

Question

我通过Dijkstra最短路径算法，在练习时我遇到了一个问题，其中顶点不是单个数字(例如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++);    
    }
}