我通过Dijkstra寻求最短路径算法时，我在练习的过程中遇到了一个问题，其中顶点不是单个数字（例如1,2,3 ...等等），但更具体地给定为（x， y）座席。我从未做过此类问题，也从未见过。您能帮我解决此类问题的方法吗？O（V ^ 2）受到热烈欢迎
使用哈希图将坐标映射到整数顶点。现在您有了一个节点为单个数字的图形。应用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++);
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句