写一个能规划最短路径的算法
时间: 2023-11-18 21:02:22 浏览: 15
Dijkstra算法是一种能规划最短路径的算法。
算法步骤:
1. 初始化:将起点标记为已访问,起点到起点的距离为0,其他节点到起点的距离为无穷大。
2. 选取当前距离起点最近的未访问节点,标记为已访问。
3. 更新当前节点的邻居节点到起点的距离,如果新距离小于之前的距离,则更新距离。
4. 重复步骤2和3,直到所有节点都被访问。
5. 最终得到起点到每个节点的最短距离。
代码实现:
```
function dijkstra(start, graph){
const visited = new Set();
const distances = {};
for(const node in graph){
distances[node] = Infinity;
}
distances[start] = 0;
while(true){
let closestNode = null;
let shortestDistance = Infinity;
for(const node in graph){
if(!visited.has(node) && distances[node] < shortestDistance){
closestNode = node;
shortestDistance = distances[node];
}
}
if(closestNode === null){
break;
}
visited.add(closestNode);
const neighbors = graph[closestNode];
for(const neighbor in neighbors){
const distance = neighbors[neighbor];
const totalDistance = distance + shortestDistance;
if(totalDistance < distances[neighbor]){
distances[neighbor] = totalDistance;
}
}
}
return distances;
}
```
该算法的时间复杂度为O(n^2),其中n为节点数,可以通过使用优先队列来优化时间复杂度为O(ElogV),其中E为边数,V为节点数。