Floyd Warshall算法，分别用C语言，C++,java,python编写出来

帆帆资源网 · 发表于 2024-2-27 12:16:57

Floyd-Warshall算法，中文称弗洛伊德算法或佛洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd Warshall算法，分别用C语言，C++,java,python编写出来
下面是Floyd-Warshall算法的不同语言实现示例：
1. C语言：

#include <stdio.h>
#define INF 99999
#define V 4
void printSolution(int dist[][V]);
void floydWarshall(int graph[][V]) {
int dist[V][V], i, j, k;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V]) {
printf("The following matrix shows the shortest distances between every pair of vertices:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
//以下为隐藏代码

复制代码

int main() {
int graph[V][V] = {{0, 5, INF, 10},
                  {INF, 0, 3, INF},
                  {INF, INF, 0, 1},
                  {INF, INF, INF, 0}};
floydWarshall(graph);
return 0;
}

2. C++:

#include <iostream>
#define INF 99999
#define V 4
void printSolution(int dist[][V]);
void floydWarshall(int graph[][V]) {
int dist[V][V], i, j, k;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][V]) {
std::cout << "The following matrix shows the shortest distances between every pair of vertices:\n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
std::cout << "INF\t";
else
std::cout << dist[i][j] << "\t";
}
std::cout << std::endl;
}
}

复制代码

int main() {
int graph[V][V] = {{0, 5, INF, 10},
                  {INF, 0, 3, INF},
                  {INF, INF, 0, 1},
                  {INF, INF, INF, 0}};
floydWarshall(graph);
return 0;
}

3. Java:

public class FloydWarshall {
static final int INF = 99999;
static final int V = 4;
void printSolution(int dist[][]) {
System.out.println("The following matrix shows the shortest distances between every pair of vertices:");
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (dist[i][j] == INF)
System.out.print("INF\t");
else
System.out.print(dist[i][j] + "\t");
}
System.out.println();
}
}
void floydWarshall(int graph[][]) {
int dist[][] = new int[V][V];
int i, j, k;
for (i = 0; i < V; ++i)
for (j = 0; j < V; ++j)
dist[i][j] = graph[i][j];
for (k = 0; k < V; ++k) {
for (i = 0; i < V; ++i) {
for (j = 0; j < V; ++j) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);

复制代码

public static void main(String[] args) {
      int graph[][] = {{0, 5, INF, 10},
                     {INF, 0, 3, INF},
                     {INF, INF, 0, 1},
                     {INF, INF, INF, 0}};
      FloydWarshall fw = new FloydWarshall();
      fw.floydWarshall(graph);
}

4. Python:

INF = 99999
V = 4
def printSolution(dist):
print("The following matrix shows the shortest distances between every pair of vertices:")
for i in range(V):
for j in range(V):
if dist[i][j] == INF:
print("INF", end="\t")
else:
print(dist[i][j], end="\t")
print()
def floydWarshall(graph):
dist = graph.copy()
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
printSolution(dist)

复制代码

graph = [[0, 5, INF, 10],
      [INF, 0, 3, INF],
      [INF, INF, 0, 1],
      [INF, INF, INF, 0]]
floydWarshall(graph)

这些示例展示了使用不同编程语言实现Floyd-Warshall算法的方式。请根据您选择的编程语言，使用相应的示例来实现Floyd-Warshall算法。

扫码关注微信公众号，免费查看完整算法内容。

		自动登录	找回密码
密码			立即注册

[其它教程] Floyd Warshall算法，分别用C语言，C++,java,python编写出来

相关帖子

客服中心

投诉建议