实际地图中dijkstra算法javascript
时间: 2023-08-20 11:04:11 浏览: 35
好的,我会为您提供一个实际地图中使用Dijkstra算法的JavaScript代码示例。
示例代码如下:
```javascript
// 定义一个Graph类来表示地图
class Graph {
constructor() {
this.vertices = [];
this.edges = {};
}
// 添加顶点
addVertex(vertex) {
this.vertices.push(vertex);
this.edges[vertex] = {};
}
// 添加边
addEdge(vertex1, vertex2, weight) {
this.edges[vertex1][vertex2] = weight;
this.edges[vertex2][vertex1] = weight;
}
}
// 实现Dijkstra算法
function dijkstra(graph, startVertex) {
const distances = {};
const visited = {};
const path = {};
const queue = [];
// 初始化距离、已访问和路径
for (let i = 0; i < graph.vertices.length; i++) {
const vertex = graph.vertices[i];
if (vertex === startVertex) {
distances[vertex] = 0;
visited[vertex] = true;
} else {
distances[vertex] = Infinity;
visited[vertex] = false;
}
path[vertex] = null;
queue.push(vertex);
}
// 遍历所有顶点
while (queue.length) {
// 找到距离最小的顶点
let minDistance = Infinity;
let minVertex = null;
for (let i = 0; i < queue.length; i++) {
const vertex = queue[i];
if (distances[vertex] < minDistance && !visited[vertex]) {
minDistance = distances[vertex];
minVertex = vertex;
}
}
// 标记已访问
visited[minVertex] = true;
// 遍历相邻顶点
const neighbors = graph.edges[minVertex];
for (let neighbor in neighbors) {
const distance = distances[minVertex] + neighbors[neighbor];
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
path[neighbor] = minVertex;
}
}
}
return { distances, path };
}
// 示例用法
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'E', 1);
graph.addEdge('D', 'E', 3);
const { distances, path } = dijkstra(graph, 'A');
console.log(distances); // { A: 0, B: 4, C: 2, D: 4, E: 3 }
console.log(path); // { A: null, B: 'A', C: 'A', D: 'C', E: 'C' }
```
这是一个简单的实现,您可以根据自己的需求进行修改和扩展。请注意,这个示例中的图是一个简单的无向图,您可以根据需要使用更复杂的图。