目录
Floyd-Warshall(弗洛伊德)算法
传递闭包
一、试题 算法训练 盾神与离散老师2
Floyd-Warshall(弗洛伊德)算法
- 求所有顶点到所有顶点的最短路径问题
- 弗洛伊德算法(Floyd-Warshall algorithm)是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。
- 该算法可以处理带有负权边但不含负权环的加权有向图或无向图。
- 弗洛伊德算法的核心思想是利用三重循环遍历所有顶点,逐步更新每对顶点之间的最短路径的信息。
弗洛伊德算法的示例代码:
import java.util.Arrays;
public class FloydWarshall {
public static void main(String[] args) {
int INF = 99999; // 表示无穷大
int[][] graph = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
}
public static void floydWarshall(int[][] graph) {
int V = graph.length;
int[][] dist = new int[V][V];
// 初始化距离矩阵为图的邻接矩阵
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 迭代更新距离矩阵
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int 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 printSolution(int[][] dist) {
int V = dist.length;
System.out.println("距离矩阵:");
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (dist[i][j] == 99999) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
}
传递闭包
- 给定一个集合,以及若干对元素之间的传递关系,传递闭包问题是求所有元素之间的传递(连通)关系。
- 例如,包括3个元素的集合{a,b,c},给定传递关系a-->b, b-->c,那么可推导出a-->c
- 用Floyd算法解决传递闭包问题
- 可用bitset优化复杂度
传递闭包的示例代码:
// 使用Floyd算法计算最短路径
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 如果经过节点k可以从节点i到达节点j,则更新传递闭包矩阵
if (matrix[i][k] == 1 && matrix[k][j] == 1) {
matrix[i][j] = 1;
}
}
}
}
一、试题 算法训练 盾神与离散老师2
问题描述
有一天,盾神觉得自己离散课快要挂了,于是亲自找到离散老师WH,请教如何才能不挂科。WH老师说,只要你做出下面那题,你就可以不挂了!但是盾神不会做T_T只能请教你了。
有N个人,i和j可能认识,可能不认识。i一定认识i。如果i认识j,j不一定认识i。但是如果i认识j,j认识k,i必定认识k。给出目前掌握的N个人互相的认识关系,求用已知的关系推断出来的N个人互相的人事关系。
输入格式
输入第一行为一个数N。
接下来是一个N*N的矩阵,第i行第j个数是1的话表示i认识j,0的话表示i不一定认识j。不会出现除0和1之外的其他数。数与数之间用一个空格隔开。第i行第i列不一定是1。
输出格式
输出一个N*N的矩阵,第i行第j列的意思如输入。数与数之间用一个空格隔开。第i行第i列必须是1。
样例输入
3
0 1 0
0 0 1
0 0 0
样例输出
1 1 1
0 1 1
0 0 1
数据规模和约定
N<=500
分析:文章来源:https://www.toymoban.com/news/detail-830513.html
- 使用Floyd算法解决,套用代码即可
- 一个三重for循环
package no1_1;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] matrix = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
scanner.nextLine();
for (int j = 1; j <= n; j++) {
matrix[i][j] = scanner.nextInt();
if(i == j) {//自己一定认识自己
matrix[i][j] = 1;
}
}
}
// 使用多重循环直接更新矩阵中的间接关系
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i][j] == 0 && matrix[i][k] == 1 && matrix[k][j] == 1) {
matrix[i][j] = 1;
}
}
}
}
//打印矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
文章来源地址https://www.toymoban.com/news/detail-830513.html
到了这里,关于算法——图论——最短路径——Floyd / 传递闭包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!