floyed算法 js
时间: 2023-10-12 09:00:35 浏览: 43
Floyd算法,也称为Floyd-Warshall算法,是一种用于解决所有点对最短路径的动态规划算法。它可以用于有向图或无向图,并且可以处理负权边。下面是Floyd算法的JavaScript实现:
```javascript
function floydWarshall(graph) {
const dist = [];
const n = graph.length;
for (let i = 0; i < n; i++) {
dist[i] = [];
for (let j = 0; j < n; j++) {
if (i === j) {
dist[i][j] = 0;
} else if (graph[i][j] === undefined) {
dist[i][j] = Infinity;
} else {
dist[i][j] = graph[i][j];
}
}
}
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
// Example usage:
const graph = [
[0, 5, undefined, 10],
[undefined, 0, 3, undefined],
[undefined, undefined, 0, 1],
[undefined, undefined, undefined, 0]
];
const shortestPaths = floydWarshall(graph);
console.log(shortestPaths);
```
在上面的