学习笔记之Floyd算法

server/2024/9/22 18:25:51/

Floyd算法是求最短路径类题目中编码复杂度最低的算法,可以说是最简单的算法了,哈哈哈

输入样例:

4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
#include<iostream>
using namespace std;int main(){int e[10][10],k,i,j,n,m,t1,t2,t3;//用inf存储一个无穷大的值 int inf=999999;//读入顶点个数和边的条数 cin>>n>>m;//初始化for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j){e[i][j]=0;}else{//若两个点之间无法直接到达,则定义为无穷大 e[i][j]=inf;}}} //读入边for(i=1;i<=m;i++){//t1,t2分别表示两个点,t3表示他们之间的距离 cin>>t1>>t2>>t3;e[t1][t2]=t3;} //Floyd算法核心语句for(k=1;k<=n;k++){for(i=1;i<=n;i++){for(j=1;j<=n;j++){//从第k号顶点中转,若比原来的值小,则更新他//实际上Floyd就是枚举了所有可能中转的方式,计算出任意两点间的最短距离 if(e[i][j]>e[i][k]+e[k][j]){e[i][j]=e[i][k]+e[k][j];}}}} //输出最终结果for(i=1;i<=n;i++){for(j=1;j<=n;j++){cout<<e[i][j]<<" ";}cout<<"\n";} return 0; 
}

输出样例

0 2 5 4
9 0 3 4
6 8 0 1
5 7 10 0

尽管Floyd算法实现起来十分容易,但是他的时间复杂度十分高,若要处理数据量比较大的数据,就不太适用了,它还无法解决“负权回路”的问题,因为“负权回路”没有最短路径,它每走一次,最短路径减1


http://www.ppmy.cn/server/120401.html

相关文章

【sgCreateCallAPIFunctionParam】自定义小工具:敏捷开发→调用接口方法参数生成工具

<template><div :class"$options.name" class"sgDevTool"><sgHead /><div class"sg-container"><div class"sg-start"><div style"margin-bottom: 10px">参数列表[逗号模式]<el-too…

c++ prime plus-5-編程練習

1, #include <iostream> using namespace std;int main() {int num1,num2,sum0;cout << "請輸入第一個整數&#xff08;較小的整數&#xff09;:";cin >> num1;cout << "請輸入第二個整數&#xff08;較大的整數&#xff09;&#xf…

Rust编写Windows服务

文章目录 Rust编写Windows服务一&#xff1a;Windows服务程序大致原理二&#xff1a;Rust中编写windows服务三&#xff1a;具体实例 Rust编写Windows服务 编写Windows服务可选语言很多, 其中C#最简单。本着练手Rust语言&#xff0c;尝试用Rust编写一个服务。 一&#xff1a;Win…

第k个排列 - 华为OD统一考试(E卷)

2024华为OD机试(E卷+D卷+C卷)最新题库【超值优惠】Java/Python/C++合集 题目描述 给定参数n,从1到n会有n个整数:1,2,3,.,n,这n个数字共有 n!种排列。按大小顺序升序列出所有排列情况,并-一标记,当n=3时,所有排列如下: “123” “132” “213” “231” “312” “…

「数组」十大排序:精讲与分析(C++)

概述 截止目前&#xff0c;我们已经讲解并分析了十种最常见的排序算法&#xff0c;下附对应文章链接和全体Code。 链接 「数组」冒泡排序|选择排序|插入排序 / 及优化方案&#xff08;C&#xff09; 「数组」归并排序 / if语句优化|小区间插入优化&#xff08;C&#xff09…

CTFShow-反序列化

一些基础&#xff1a; private变量会被序列化为&#xff1a;\x00类名\x00变量名 protected变量会被序列化为: \x00*\x00变量名 public变量会被序列化为&#xff1a;变量名 __sleep() //在对象被序列化之前运行 * __wakeup() //将在反序列化之后立即调用&#xff08;当反序列化时…

天安门广场预约分析

首先&#xff0c;我们进入到首页&#xff0c;https://yuyue.tamgw.beijing.gov.cn/index.html&#xff0c;我们选择个人预约信息。 第一个比较重要的参数playDate&#xff0c;就是预约日期&#xff0c;一般可以预约未来1-7天的不同时间段&#xff0c;这里我们选择好固定的日期…

鸿蒙OpenHarmony【轻量系统芯片移植】轻量系统STM32F407芯片移植案例

轻量系统STM32F407芯片移植案例 介绍基于STM32F407IGT6芯片在拓维信息[Niobe407]开发板上移植OpenHarmony LiteOS-M轻量系统&#xff0c;提供交通、工业领域开发板解决方案。移植架构采用Board与SoC分离方案&#xff0c;使用arm gcc工具链Newlib C库&#xff0c;实现了lwip、l…