写一份Floyd算法的代码
时间: 2023-03-14 12:00:05 浏览: 61
我可以给你提供一个示例:def floyd(matrix):
n = len(matrix)
for k in range(n):
for i in range(n):
for j in range(n):
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
return matrix print(floyd([[0, 2, 999, 1],
[3, 0, 999, 4],
[999, 5, 0, 999],
[6, 999, 2, 0]]))
相关问题
用JavaScript写一个floyd算法
Floyd算法是一种用于求解最短路径的算法,它是一种动态规划算法。下面是使用JavaScript实现的Floyd算法:
```javascript
function floyd(graph) {
const n = graph.length;
const dist = [];
// 初始化距离矩阵
for (let i = 0; i < n; i++) {
dist[i] = [];
for (let j = 0; j < n; j++) {
if (graph[i][j] === undefined) {
dist[i][j] = Infinity;
} else {
dist[i][j] = graph[i][j];
}
}
}
// Floyd算法核心代码
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
// 测试代码
const graph = [
[0, 1, 4, undefined, undefined],
[1, 0, 2, 7, 5],
[4, 2, 0, 1, undefined],
[undefined, 7, 1, 0, 3],
[undefined, 5, undefined, 3, 0]
];
console.log(floyd(graph));
```
在上面的代码中,我们首先将输入的邻接矩阵拷贝到一个距离矩阵中,如果两个顶点之间没有边相连,则距离设为无穷大。然后,我们使用三重循环来实现Floyd算法的核心部分,即更新距离矩阵。最后,我们返回更新后的距离矩阵。在测试代码中,我们使用一个图来测试我们的算法。
用c语言写一个floyd算法
我可以为您提供一个c语言实现的Floyd算法的示例代码: // Floyd算法:
#define N 100 // 图的顶点数
int dis[N][N]; // 邻接矩阵
// 初始化
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dis[i][j] = (i == j) ? 0 : INF; // INF表示两点不可达 // Floyd算法
for (int k = 0; k < N; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);