From f3c59a17062fb0a89b5f89b7845341386952a6b1 Mon Sep 17 00:00:00 2001
From: rk <94314517@qq.com>
Date: 星期三, 24 九月 2025 16:01:06 +0800
Subject: [PATCH] Merge remote-tracking branch 'origin/master'
---
server/system_service/src/main/java/com/doumee/core/utils/DijkstraUtil.java | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 108 insertions(+), 0 deletions(-)
diff --git a/server/system_service/src/main/java/com/doumee/core/utils/DijkstraUtil.java b/server/system_service/src/main/java/com/doumee/core/utils/DijkstraUtil.java
new file mode 100644
index 0000000..6cd9413
--- /dev/null
+++ b/server/system_service/src/main/java/com/doumee/core/utils/DijkstraUtil.java
@@ -0,0 +1,108 @@
+package com.doumee.core.utils;
+
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.Queue;
+
+public class DijkstraUtil {
+ private Queue visited;
+ int[] distance;
+
+ public DijkstraUtil(int len) {
+ // TODO Auto-generated constructor stub
+ visited = new LinkedList();
+ distance = new int[len];
+
+ }
+
+ private int getIndex(Queue q, int[] dis) {
+ int k = -1;
+ int min_num = Integer.MAX_VALUE;
+ for (int i = 0; i < dis.length; i++) {
+ if (!q.contains(i)) {
+ if (dis[i] < min_num) {
+ min_num = dis[i];
+ k = i;
+ }
+ }
+ }
+ return k;
+ }
+
+ public void dijkstra(int[][] weight, Object[] str, int v) {
+ HashMap path;
+ path = new HashMap();
+ for (int i = 0; i < str.length; i++)
+ path.put(i, "");
+
+ //鍒濆鍖栬矾寰勯暱搴︽暟缁刣istance
+ for (int i = 0; i < str.length; i++) {
+ path.put(i, path.get(i) + "" + str[v]);
+ if (i == v)
+ distance[i] = 0;
+ else if (weight[v][i] != -1) {
+ distance[i] = weight[v][i];
+ path.put(i, path.get(i) + "-->" + str[i]);
+ } else
+ distance[i] = Integer.MAX_VALUE;
+ }
+ visited.add(v);
+ while (visited.size() < str.length) {
+ int k = getIndex(visited, distance);//鑾峰彇鏈闂偣涓窛绂绘簮鐐规渶杩戠殑鐐�
+ visited.add(k);
+ if (k != -1) {
+
+ for (int j = 0; j < str.length; j++) {
+ //鍒ゆ柇k鐐硅兘澶熺洿鎺ュ埌杈剧殑鐐�
+ if (weight[k][j] != -1) {
+ //閫氳繃閬嶅巻鍚勭偣锛屾瘮杈冩槸鍚︽湁姣斿綋鍓嶆洿鐭殑璺緞锛屾湁鐨勮瘽锛屽垯鏇存柊distance锛屽苟鏇存柊path銆�
+ if (distance[j] > distance[k] + weight[k][j]) {
+ distance[j] = distance[k] + weight[k][j];
+ path.put(j, path.get(k) + "-->" + str[j]);
+ }
+ }
+
+ }
+ }
+ }
+ for (int h = 0; h < str.length; h++) {
+ System.out.printf(str[v] + "-->" + str[h] + ":" + distance[h] + " ");
+ if (distance[h] == Integer.MAX_VALUE)
+ System.out.print(str[v] + "-->" + str[h] + "涔嬮棿娌℃湁鍙�氳璺緞");
+ else
+ System.out.print(str[v] + "-" + str[h] + "涔嬮棿鏈夋渶鐭矾寰勶紝鍏蜂綋璺緞涓猴細" + path.get(h).toString());
+ System.out.println();
+ }
+ visited.clear();
+
+ }
+
+ public static void main(String[] args) {
+ // TODO Auto-generated method stub
+ /* int[][] weight = {
+ {0, 10, 12, -1, -1, -1},
+ {-1, 0, -1, 16, 25, -1},
+ {4, 3, 0, 12, -1, 8},
+ {-1, -1, -1, 0, 7, -1},
+ {-1, -1, -1, -1, 0, -1},
+ {-1, -1, -1, 2, -1, 0}};
+ String[] str = {"V1", "V2", "V3", "V4", "V5", "V6"};
+ int len = str.length;
+ DijkstraUtil dijkstra = new DijkstraUtil(len);
+ //渚濇璁╁悇鐐瑰綋婧愮偣锛屽苟璋冪敤dijkstra鍑芥暟
+ for (int i = 0; i < str.length; i++) {
+ dijkstra.dijkstra(weight, str, i);
+ }*/
+
+ int[][] weight = {
+ {0, 10, 5, 7, -1},
+ {-1, 0, 4, 5, 10},
+ {-1, 4, 0, 6, 5},
+ {-1, 5, 6, 0, 7},
+ {-1, -1, -1, -1, 0}};
+ String[] str = {"A", "B", "C", "D", "E"};
+ DijkstraUtil dijkstra = new DijkstraUtil(str.length);
+ dijkstra.dijkstra(weight, str, 0);
+ }
+
+}
--
Gitblit v1.9.3