class065 A星、Floyd、Bellman-Ford與SPFA【算法】

class065 A星、Floyd、Bellman-Ford與SPFA【算法】

2023-12-9 19:27:02

算法講解065【必備】A星、Floyd、Bellman-Ford與SPFA

在這里插入圖片描述

在這里插入圖片描述
在這里插入圖片描述

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

code1 A*算法模版

// A*算法模版（對數器驗證）

package class065;import java.util.PriorityQueue;// A*算法模版（對數器驗證）
public class Code01_AStarAlgorithm {// 0:上，1:右，2:下，3:左public static int[] move = new int[] { -1, 0, 1, 0, -1 };// Dijkstra算法// grid[i][j] == 0 代表障礙// grid[i][j] == 1 代表道路// 只能走上、下、左、右，不包括斜線方向// 返回從(startX, startY)到(targetX, targetY)的最短距離public static int minDistance1(int[][] grid, int startX, int startY, int targetX, int targetY) {if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) {return -1;}int n = grid.length;int m = grid[0].length;int[][] distance = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {distance[i][j] = Integer.MAX_VALUE;}}distance[startX][startY] = 1;boolean[][] visited = new boolean[n][m];PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);// 0 : 行// 1 : 列// 2 : 從源點出發到達當前點的距離heap.add(new int[] { startX, startY, 1 });while (!heap.isEmpty()) {int[] cur = heap.poll();int x = cur[0];int y = cur[1];if (visited[x][y]) {continue;}visited[x][y] = true;if (x == targetX && y == targetY) {return distance[x][y];}for (int i = 0, nx, ny; i < 4; i++) {nx = x + move[i];ny = y + move[i + 1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny]&& distance[x][y] + 1 < distance[nx][ny]) {distance[nx][ny] = distance[x][y] + 1;heap.add(new int[] { nx, ny, distance[x][y] + 1 });}}}return -1;}// A*算法// grid[i][j] == 0 代表障礙// grid[i][j] == 1 代表道路// 只能走上、下、左、右，不包括斜線方向// 返回從(startX, startY)到(targetX, targetY)的最短距離public static int minDistance2(int[][] grid, int startX, int startY, int targetX, int targetY) {if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) {return -1;}int n = grid.length;int m = grid[0].length;int[][] distance = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {distance[i][j] = Integer.MAX_VALUE;}}distance[startX][startY] = 1;boolean[][] visited = new boolean[n][m];// 0 : 行// 1 : 列// 2 : 從源點出發到達當前點的距離 + 當前點到終點的預估距離PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);heap.add(new int[] { startX, startY, 1 + f1(startX, startY, targetX, targetY) });while (!heap.isEmpty()) {int[] cur = heap.poll();int x = cur[0];int y = cur[1];if (visited[x][y]) {continue;}visited[x][y] = true;if (x == targetX && y == targetY) {return distance[x][y];}for (int i = 0, nx, ny; i < 4; i++) {nx = x + move[i];ny = y + move[i + 1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny]&& distance[x][y] + 1 < distance[nx][ny]) {distance[nx][ny] = distance[x][y] + 1;heap.add(new int[] { nx, ny, distance[x][y] + 1 + f1(nx, ny, targetX, targetY) });}}}return -1;}// 曼哈頓距離public static int f1(int x, int y, int targetX, int targetY) {return (Math.abs(targetX - x) + Math.abs(targetY - y));}// 對角線距離public static int f2(int x, int y, int targetX, int targetY) {return Math.max(Math.abs(targetX - x), Math.abs(targetY - y));}// 歐式距離public static double f3(int x, int y, int targetX, int targetY) {return Math.sqrt(Math.pow(targetX - x, 2) + Math.pow(targetY - y, 2));}// 為了測試public static int[][] randomGrid(int n) {int[][] grid = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (Math.random() < 0.3) {// 每個格子有30%概率是0grid[i][j] = 0;} else {// 每個格子有70%概率是1grid[i][j] = 1;}}}return grid;}// 為了測試public static void main(String[] args) {int len = 100;int testTime = 10000;System.out.println("功能測試開始");for (int i = 0; i < testTime; i++) {int n = (int) (Math.random() * len) + 2;int[][] grid = randomGrid(n);int startX = (int) (Math.random() * n);int startY = (int) (Math.random() * n);int targetX = (int) (Math.random() * n);int targetY = (int) (Math.random() * n);int ans1 = minDistance1(grid, startX, startY, targetX, targetY);int ans2 = minDistance2(grid, startX, startY, targetX, targetY);if (ans1 != ans2) {System.out.println("出錯了!");}}System.out.println("功能測試結束");System.out.println("性能測試開始");int[][] grid = randomGrid(4000);int startX = 0;int startY = 0;int targetX = 3900;int targetY = 3900;long start, end;start = System.currentTimeMillis();int ans1 = minDistance1(grid, startX, startY, targetX, targetY);end = System.currentTimeMillis();System.out.println("運行dijskra算法結果: " + ans1 + ", 運行時間(毫秒) : " + (end - start));start = System.currentTimeMillis();int ans2 = minDistance2(grid, startX, startY, targetX, targetY);end = System.currentTimeMillis();System.out.println("運行A*算法結果: " + ans2 + ", 運行時間(毫秒) : " + (end - start));System.out.println("性能測試結束");}}

code2 P2910 [USACO08OPEN] Clear And Present Danger S

// Floyd算法模版（洛谷）
// 測試鏈接 : https://www.luogu.com.cn/problem/P2910
// 請同學們務必參考如下代碼中關于輸入、輸出的處理
// 這是輸入輸出處理效率很高的寫法
// 提交以下所有代碼，把主類名改成Main，可以直接通過

package class065;// Floyd算法模版（洛谷）
// 測試鏈接 : https://www.luogu.com.cn/problem/P2910
// 請同學們務必參考如下代碼中關于輸入、輸出的處理
// 這是輸入輸出處理效率很高的寫法
// 提交以下所有代碼，把主類名改成Main，可以直接通過import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Code02_Floyd {public static int MAXN = 101;public static int MAXM = 10001;public static int[] path = new int[MAXM];public static int[][] distance = new int[MAXN][MAXN];public static int n, m, ans;// 初始時設置任意兩點之間的最短距離為無窮大，表示任何路不存在public static void build() {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {distance[i][j] = Integer.MAX_VALUE;}}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() != StreamTokenizer.TT_EOF) {n = (int) in.nval;in.nextToken();m = (int) in.nval;for (int i = 0; i < m; i++) {in.nextToken();path[i] = (int) in.nval - 1;}// 這道題給的圖是鄰接矩陣的形式// 任意兩點之間的邊權都會給定// 所以顯得distance初始化不太必要// 但是一般情況下，distance初始化一定要做build();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {in.nextToken();distance[i][j] = (int) in.nval;}}floyd();ans = 0;for (int i = 1; i < m; i++) {ans += distance[path[i - 1]][path[i]];}out.println(ans);}out.flush();out.close();br.close();}public static void floyd() {// O(N^3)的過程// 枚舉每個跳板// 注意，跳板要最先枚舉！跳板要最先枚舉！跳板要最先枚舉！for (int bridge = 0; bridge < n; bridge++) { // 跳板for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// i -> .....bridge .... -> j// distance[i][j]能不能縮短// distance[i][j] = min ( distance[i][j] , distance[i][bridge] + distance[bridge][j])if (distance[i][bridge] != Integer.MAX_VALUE && distance[bridge][j] != Integer.MAX_VALUE&& distance[i][j] > distance[i][bridge] + distance[bridge][j]) {distance[i][j] = distance[i][bridge] + distance[bridge][j];}}}}}}

code3 787. K 站中轉內最便宜的航班

// Bellman-Ford算法應用（不是模版）
// k站中轉內最便宜的航班
// 有 n 個城市通過一些航班連接。給你一個數組 flights
// 其中 flights[i] = [fromi, toi, pricei]
// 表示該航班都從城市 fromi 開始，以價格 pricei 抵達 toi。
// 現在給定所有的城市和航班，以及出發城市 src 和目的地 dst，你的任務是找到出一條最多經過 k 站中轉的路線
// 使得從 src 到 dst 的 價格最便宜 ，并返回該價格。 如果不存在這樣的路線，則輸出 -1。
// 測試鏈接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/

package class065;import java.util.Arrays;// Bellman-Ford算法應用（不是模版）
// k站中轉內最便宜的航班
// 有 n 個城市通過一些航班連接。給你一個數組 flights
// 其中 flights[i] = [fromi, toi, pricei]
// 表示該航班都從城市 fromi 開始，以價格 pricei 抵達 toi。
// 現在給定所有的城市和航班，以及出發城市 src 和目的地 dst，你的任務是找到出一條最多經過 k 站中轉的路線
// 使得從 src 到 dst 的 價格最便宜 ，并返回該價格。 如果不存在這樣的路線，則輸出 -1。
// 測試鏈接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/
public class Code03_BellmanFord {// Bellman-Ford算法// 針對此題改寫了松弛邏輯，課上講了細節public static int findCheapestPrice(int n, int[][] flights, int start, int target, int k) {int[] cur = new int[n];Arrays.fill(cur, Integer.MAX_VALUE);cur[start] = 0;for (int i = 0; i <= k; i++) {int[] next = Arrays.copyOf(cur, n);for (int[] edge : flights) {// a -> b , wif (cur[edge[0]] != Integer.MAX_VALUE) {next[edge[1]] = Math.min(next[edge[1]], cur[edge[0]] + edge[2]);}}cur = next;}return cur[target] == Integer.MAX_VALUE ? -1 : cur[target];}}

P3385 【模板】負環

// Bellman-Ford + SPFA優化模版（洛谷）
// 給定一個 n個點的有向圖，請求出圖中是否存在從頂點 1 出發能到達的負環
// 負環的定義是：一條邊權之和為負數的回路。
// 測試鏈接 : https://www.luogu.com.cn/problem/P3385
// 請同學們務必參考如下代碼中關于輸入、輸出的處理
// 這是輸入輸出處理效率很高的寫法
// 提交以下所有代碼，把主類名改成Main，可以直接通過

package class065;// Bellman-Ford + SPFA優化模版（洛谷）
// 給定一個 n個點的有向圖，請求出圖中是否存在從頂點 1 出發能到達的負環
// 負環的定義是：一條邊權之和為負數的回路。
// 測試鏈接 : https://www.luogu.com.cn/problem/P3385
// 請同學們務必參考如下代碼中關于輸入、輸出的處理
// 這是輸入輸出處理效率很高的寫法
// 提交以下所有代碼，把主類名改成Main，可以直接通過import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Code04_SPFA {public static int MAXN = 2001;public static int MAXM = 6001;// 鏈式前向星建圖需要public static int[] head = new int[MAXN];public static int[] next = new int[MAXM];public static int[] to = new int[MAXM];public static int[] weight = new int[MAXM];public static int cnt;// SPFA需要public static int MAXQ = 4000001;// 源點出發到每個節點的距離表public static int[] distance = new int[MAXN];// 節點被松弛的次數public static int[] updateCnt = new int[MAXN];// 哪些節點被松弛了放入隊列public static int[] queue = new int[MAXQ];public static int l, r;// 節點是否已經在隊列中public static boolean[] enter = new boolean[MAXN];public static void build(int n) {cnt = 1;l = r = 0;Arrays.fill(head, 1, n + 1, 0);Arrays.fill(enter, 1, n + 1, false);Arrays.fill(distance, 1, n + 1, Integer.MAX_VALUE);Arrays.fill(updateCnt, 1, n + 1, 0);}public static void addEdge(int u, int v, int w) {next[cnt] = head[u];to[cnt] = v;weight[cnt] = w;head[u] = cnt++;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int cases = (int) in.nval;for (int i = 0, n, m; i < cases; i++) {in.nextToken(); n = (int) in.nval;in.nextToken(); m = (int) in.nval;build(n);for (int j = 0, u, v, w; j < m; j++) {in.nextToken(); u = (int) in.nval;in.nextToken(); v = (int) in.nval;in.nextToken(); w = (int) in.nval;if (w >= 0) {addEdge(u, v, w);addEdge(v, u, w);} else {addEdge(u, v, w);}}out.println(spfa(n) ? "YES" : "NO");}out.flush();out.close();br.close();}// Bellman-Ford + SPFA優化的模版public static boolean spfa(int n) {distance[1] = 0;updateCnt[1]++;queue[r++] = 1;enter[1] = true;while (l < r) {int u = queue[l++];enter[u] = false;for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {v = to[ei];w = weight[ei];if (distance[u] + w < distance[v]) {distance[v] = distance[u] + w;if (!enter[v]) {if (updateCnt[v]++ == n) {return true;}queue[r++] = v;enter[v] = true;}}}}return false;}}

2023-12-9 21:16:55

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/210116.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/210116.shtml
英文地址，請注明出處：http://en.pswp.cn/news/210116.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

vue3+TypeScript全局事件總線mitt

vue3+TypeScript全局事件總線mitt

在vue3中 $ on&#xff0c;$off 和 $once 實例方法已被移除&#xff0c;組件實例不再實現事件觸發接口&#xff0c;因此大家熟悉的EventBus便無法使用了。然而我們習慣了使用EventBus&#xff0c;對于這種情況我們可以使用Mitt庫 npm i mitt -S 首先要在全局掛載 mitt 在app…
閱讀更多...
兩年外包生涯做完，感覺自己廢了一半。。。。。

兩年外包生涯做完，感覺自己廢了一半。。。。。

先說一下自己的情況&#xff0c;本科生&#xff0c;19年通過校招進入南京某軟件公司&#xff0c;干了接近2年的功能測試&#xff0c;今年年初&#xff0c;感覺自己不能夠在這樣下去了&#xff0c;長時間呆在一個舒適的環境會讓一個人墮落!而我已經在一個企業干了2年的功能測試&…
閱讀更多...
laravel的ORM 對象關系映射

laravel的ORM 對象關系映射

Laravel 中的 ORM&#xff08;Eloquent ORM&#xff09;是 Laravel 框架內置的一種對象關系映射系統&#xff0c;用于在 PHP 應用中與數據庫進行交互。Eloquent 提供了一種優雅而直觀的語法&#xff0c;使得開發者可以使用面向對象的方式進行數據庫查詢和操作。 定義模型&…
閱讀更多...
結合ColorUI組件開發微信小程序

結合ColorUI組件開發微信小程序

1.自定義組件生命周期函數&#xff1a; Component({data: {},attached() {console.log("自定義組件生命周期函數 attached--先執行");this.getPos();},ready() {console.log("ready生命周期函數---在attached之后執行")},methods: {getPos() {var that th…
閱讀更多...
數據結構：位圖、布隆過濾器以及海量數據面試題

數據結構：位圖、布隆過濾器以及海量數據面試題

位圖、布隆過濾器以及海量數據面試題 1.位圖1.1概念1.2實現1.3位圖應用 2.布隆過濾器2.1布隆過濾器的提出2.2布隆過濾器的概念2.3布隆過濾器的查找2.4布隆過濾器的實現2.5布隆過濾器的刪除2.6布隆過濾器的優點2.7布隆過濾器的缺點 3.海量數據面試題3.1哈希切分3.2位圖應用3.3布…
閱讀更多...
如何成為前1%的程序員

如何成為前1%的程序員

如果你想成為前1%的程序員&#xff0c;你必須遵循1%的程序員做什么&#xff0c;了解其他99%的人不做什么。在現代&#xff0c;我們有各種學習平臺&#xff0c;里面充滿了與編程相關的視頻、圖文以及其他資料。 舉例來說&#xff0c;我作為編程的初學者&#xff0c;去尋找路線圖…
閱讀更多...
IDEA2023找不到add framework support怎么解決

IDEA2023找不到add framework support怎么解決

問題: 我的idea版本是2023.01&#xff0c;新版idea右鍵項目沒有Add Framework Support&#xff0c;help里面也找不到相關的。 從project structue的facets里面添加就行了&#xff0c;都是一樣的。 1.依舊是新建一個項目 2.file-->project structure--->facets 左上角加…
閱讀更多...
數據結構與程序的關系

數據結構與程序的關系

在計算機科學中，數據結構和算法是兩個核心的概念。數據結構是程序的基礎，它組織和存儲數據的方式直接影響程序的設計、效率、可讀性以及程序的錯誤檢測和調試。本文將詳細討論數據結構如何影響程序，以及數據結構與算法的組合如何使程序更高效、可靠。 一、數據結構的選擇影…
閱讀更多...
Android studio如何安裝ai輔助工具

Android studio如何安裝ai輔助工具

引言 在沒有翻墻的情況下&#xff0c;即單純在公司打工&#xff0c;經測試&#xff0c;大部分ai工具都是使用不了的&#xff08;比如各種gpt,codeium,copilot&#xff09;&#xff0c;根本登錄不了賬號&#xff0c;但有一個國內的codegeex是可以使用的&#xff0c;在這里不對各…
閱讀更多...
tensorflow中張量tensor

tensorflow中張量tensor

在 TensorFlow 中&#xff0c;主要操作的對象是張量&#xff08;tf.Tensor&#xff09;。張量表示一個多維數組&#xff0c;可以執行各種操作以構建和修改計算圖。以下是一些常見的 TensorFlow 張量操作&#xff1a; 1. 創建張量&#xff1a; 使用 tf.constant 創建常量張量。…
閱讀更多...
Android app性能優化指南

Android app性能優化指南

Android應用性能優化指南 提高應用程序的性能以實現更流暢的用戶體驗和更高的可見度。 性能在任何應用程序的成功中發揮著重要的作用。為用戶提供流暢無縫的體驗應該是開發人員的重點。 應用程序大小 在用戶開始使用我們的應用程序之前&#xff0c;他們需要下載應用程序并將…
閱讀更多...
DTCC2023大會-DBdoctor-基于eBPF觀測數據庫-附所有PPT下載鏈接

DTCC2023大會-DBdoctor-基于eBPF觀測數據庫-附所有PPT下載鏈接

DTCC2023大會-DBdoctor-基于eBPF觀測數據庫-附所有PPT下載鏈接 8月16日—18日,第14屆中國數據庫技術大會(DTCC-2023)在北京國際會議中心舉行。聚好看在大會上首次發布基于eBPF觀測數據庫性能的產品DBdoctor&#xff0c;受到了業界廣泛的關注。近期幾位業內同仁過來要大會的PPT…
閱讀更多...
2024考研數學二備考歷程

2024考研數學二備考歷程

GoodNotesGoodNotes apphttps://share.goodnotes.com/s/bhsraJMZ6OJwuYJb3OWnzP
閱讀更多...
Python點云處理（二十）點云輪廓邊界提取——基于鄰域三角形距離算法

Python點云處理（二十）點云輪廓邊界提取——基于鄰域三角形距離算法

目錄 0 簡述1 點云輪廓提取原理2 點云輪廓提取應用3 算法步驟4 代碼實現5 結果展示0 簡述 點云輪廓提取/邊界提取，對于掃描物信息化提取、矢量化等都具有很重要的意義。掃描物體輪廓不僅包含位置和形狀信息，而且可作為一種先驗形狀信息推斷其結構以輔助三維模型重建，因此輪…
閱讀更多...
C/C++之輸入輸出

C/C++之輸入輸出

文章目錄 一.C語言的輸入輸出1.printfi. 輸出整數ii. 浮點數iii.字符 & 字符串 2.scanfi.整數ii.浮點數iii. 字符 & 字符串 3.特殊用法i. * 的應用ii. %n 的應用iii. %[] 的應用 二.C中的輸入輸出1.couti. 緩沖區&#xff08;buffer&#xff09;ii. cout之格式化輸出 2…
閱讀更多...
Proteus仿真--串口發送數據到2片8×8點陣屏滾動顯示

Proteus仿真--串口發送數據到2片8×8點陣屏滾動顯示

本文介紹2片88點陣屏滾動顯示設計&#xff08;完整仿真源文件及代碼見文末鏈接&#xff09; 仿真圖如下 仿真運行視頻 Proteus仿真--1602LCD顯示電話撥號鍵盤按鍵實驗&#xff08;仿真文件程序&#xff09; 附完整Proteus仿真資料代碼資料 鏈接&#xff1a;https://pan.baidu…
閱讀更多...
【python】函數的參數（實參，形參，*args和**kwargs）

【python】函數的參數（實參，形參，*args和**kwargs）

一、實參和形參 實參&#xff1a; 函數執行的時候給函數傳遞的具體的值 形參&#xff1a; 在函數聲明時編寫的變量 函數執行時每個形參都要有值 # a,b為形參 def add(a, b):print(a b) # 3,4為實參 add(3, 4)二、實參 1.位置參數 按位置給形參傳遞數據 def add(a, b)…
閱讀更多...
使用C語言操作kafka ---- librdkafka

使用C語言操作kafka ---- librdkafka

1 安裝librdkafka git clone https://github.com/edenhill/librdkafka.git cd librdkafka git checkout v1.7.0 ./configure make sudo make install sudo ldconfig 在librdkafka的examples目錄下會有示例程序。比如consumer的啟動需要下列參數 ./consumer <broker> &…
閱讀更多...
一對一聊天程序

一對一聊天程序

package untitled1.src;import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.io.*; import java.net.*;public class MyServer extends JFrame{private ServerSocket server; // 服務器套接字pri…
閱讀更多...
【漏洞復現】華脈智聯指揮調度平臺/xml_edit/fileread.php文件讀取漏洞

【漏洞復現】華脈智聯指揮調度平臺/xml_edit/fileread.php文件讀取漏洞

Nx01 產品簡介 深圳市華脈智聯科技有限公司&#xff0c;融合通信系統將公網集群系統、專網寬帶集群系統、不同制式、不同頻段的短波/超短波對講、模擬/數字集群系統、辦公電話系統、廣播系統、集群單兵視頻、視頻監控系統、視頻會議系統等融為一體&#xff0c;集成了專業的有線…
閱讀更多...
最新文章

Copyright @ 2022~2023