065A星,Floyd,Bellman-Ford与SPFA

发表于2025-09-15|更新于2025-09-15|[object Object]

|浏览量:

A*算法
源点到目标点

文章作者: yzr

文章链接: http://example.com/2025/09/15/065A%E6%98%9F-Floyd-Bellman-Ford%E4%B8%8ESPFA/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源言和和和！

相关推荐

025堆结构和堆排序

堆（Heap）是什么？堆是一种特殊的完全二叉树，它满足以下两个关键性质：结构性：它必须是一棵完全二叉树，这意味着除了最后一层，其他所有层都是完全满的，并且最后一层的节点都靠左排列。这种结构使得它可以用一个简单的数组来高效存储。堆序性：每个节点的值都必须满足特定的关系。大顶堆（Max-Heap）：每个父节点的值都大于或等于其子节点的值。小顶堆（Min-Heap）：每个父节点的值都小于或等于其子节点的值。在数组中，如果节点从索引 1 开始，那么父子关系可以通过简单的公式计算：父节点：i/2左孩子：2i右孩子：2i+1 时间复杂度Onlogn 用常量增倍法把n个数建立堆上限是n个数依次进入第n个高度logn 所以上限nlogn假设2n个数是否以这个做下限后n个数高度大于logn 为什么是上限也是下限说明只能是它输出前m个小的数 import java.util.Scanner; public class Main { // N: 堆的最大容量 // h: 存储堆元素的数组，索引从1开始 // size: 堆中当前元素的...

左程云019输入输出的处理

ACM 风格的 I/O 与内存管理在算法竞赛（ACM）中，程序的执行效率至关重要。除了算法复杂度，I/O 和内存管理的开销也对性能有着决定性的影响。ACM 风格的编程追求极致的效率，其核心在于 I/O 缓冲和静态内存分配。高效 I/O：BufferedReader 与 Scanner 的对比在 Java 中，Scanner 类提供了一个便利的接口，但其内部实现涉及频繁的底层 I/O 操作。每次调用 Scanner.nextInt() 或 Scanner.next()，都可能触发一次对系统 I/O 流的访问，这带来了显著的性能开销。相比之下，BufferedReader 采用了一种缓冲机制来优化 I/O 性能。它在内存中维护一个缓冲区（默认大小为 8KB），并一次性从底层数据源（如 System.in）读取一大块数据。后续的读取请求都在这个内存缓冲区内完成，从而显著减少了对底层 I/O 设备的访问次数。同样，为了优化输出，ACM 风格的程序会使用 PrintWriter 或 Buffere...

1.一开始元素拥有自己的集合，在自己的集合里只有这个元素自己2.find(i):查找i所在集合的代表元素，代表元素来代表i所在的集合3.boolean isSameSet(a,b):判断a,b在不在一个集合里4.void union(a,b):a所在集合所有元素和b所在集合所有元素合并成一个集合5.各种操作单次调用的均摊时间复杂度O(1) find一直往上找一直找到不能再往上的优化一 union小的去挂大的优化二扁平化(路径压缩)比如说 2-3 3-4 4-5find(2)的时候在找父节点的过程中我们把沿途的都给直接挂到5那越调用速度越快，挺好 father 和 size的改变只有代表节点的size信息有用也就是最上方的节点对吧father指向父节点 import java.io.*; public class Main { // n 和 m 为题目给定的总数和操作数 static int n, m; // father[i] 存储 i 的父节点 static int[] father; // size[i] 存...

044前缀树原理和代码

没有路就新建节点:已经有路就复用节点 p值就是以他开头的有多少个e值就是这个字符串出现了几次题目一 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687import java.util.HashSet;// 数组中两个数的最大异或值// 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0<=i<=j<=n// 1 <= nums.length <= 2 * 10^5// 0 <= nums[i] <= 2^31 - 1// 测试链接 : https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/public class Code02_Tw...

059拓扑排序

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768import java.util.ArrayList;class Solution {/*** 找到所有课程的正确学习顺序。* 这个问题可以建模为一个有向无环图（DAG）的拓扑排序问题。** @param numCourses 课程总数* @param prerequisites 先决条件数组，prerequisites[i] = [ai, bi] 表示学习课程 ai 之前必须先学习课程 bi* @return 课程的有效学习顺序，如果不存在（图中存在环），则返回一个空数组*/public int[] findOrder(int numCourses, int[][] prerequisites) {// 1. 建立邻接表（图）和入度表ArrayList<ArrayList<Integer>...

061最小生成树

最小生成树:在无向带权图中选择一些边，在保证连通性的情况下，边的总权值最小最小生成树可能不只一棵，只要保证边的总权值最小，就是正确的最小生成树。如果无向带权图有n个点，那么最小生成树一定有n-1条边 Kruskal算法(最常用)1 把所有的边，根据权值从小到大排序，从权值小的边开始考虑2 如果连接当前的边不会形成环，就选择3 如果连接当前的边会形成环，就不选4 考察完所有的边，就得到最小生成树用并查集来判断会不会形成环 P3366 【模板】最小生成树题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。输入格式第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。输出格式如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。输入输出样例 #1输入 #11234564 51 2 21 3 21 4 32 3 43 4 3 输出 #117 说明&#x...

评论