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/GraphByMatrix.java | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 258 insertions(+), 0 deletions(-)
diff --git a/server/system_service/src/main/java/com/doumee/core/utils/GraphByMatrix.java b/server/system_service/src/main/java/com/doumee/core/utils/GraphByMatrix.java
new file mode 100644
index 0000000..77f5a8b
--- /dev/null
+++ b/server/system_service/src/main/java/com/doumee/core/utils/GraphByMatrix.java
@@ -0,0 +1,258 @@
+package com.doumee.core.utils;
+
+import java.util.*;
+
+/**
+ * 鏈�鐭矾寰勨�擠ijkstra绠楁硶鍜孎loyd绠楁硶
+ * Dijkstra(杩澃鏂壒鎷�)绠楁硶鏄吀鍨嬬殑鍗曟簮鏈�鐭矾寰勭畻娉曪紝鐢ㄤ簬璁＄畻涓�涓妭鐐瑰埌鍏朵粬鎵�鏈夎妭鐐圭殑鏈�鐭矾寰勩�備富瑕佺壒鐐规槸浠ヨ捣濮嬬偣涓轰腑蹇冨悜澶栧眰灞傛墿灞曪紝鐩村埌鎵╁睍鍒扮粓鐐逛负姝€�侱ijkstra绠楁硶鏄緢鏈変唬琛ㄦ�х殑鏈�鐭矾寰勭畻娉曪紝鍦ㄥ緢澶氫笓涓氳绋嬩腑閮戒綔涓哄熀鏈唴瀹规湁璇︾粏鐨勪粙缁嶏紝濡傛暟鎹粨鏋勶紝鍥捐锛岃繍绛瑰绛夌瓑銆傛敞鎰忚绠楁硶瑕佹眰鍥句腑涓嶅瓨鍦ㄨ礋鏉冭竟銆�
+ *
+ * 闂鎻忚堪锛氬湪鏃犲悜鍥� G=(V,E) 涓紝鍋囪姣忔潯杈� E[i] 鐨勯暱搴︿负 w[i]锛屾壘鍒扮敱椤剁偣 V0 鍒板叾浣欏悇鐐圭殑鏈�鐭矾寰勩�傦紙鍗曟簮鏈�鐭矾寰勶級
+ */
+
+public class GraphByMatrix {
+ public static final boolean UNDIRECTED_GRAPH = false;//鏃犲悜鍥炬爣蹇�
+ public static final boolean DIRECTED_GRAPH = true;//鏈夊悜鍥炬爣蹇�
+
+ public static final boolean ADJACENCY_MATRIX = true;//閭绘帴鐭╅樀瀹炵幇
+ public static final boolean ADJACENCY_LIST = false;//閭绘帴琛ㄥ疄鐜�
+
+ public static final int MAX_VALUE = Integer.MAX_VALUE;
+ private boolean graphType;
+ private boolean method;
+ private int vertexSize;
+ private int matrixMaxVertex;
+
+ //瀛樺偍鎵�鏈夐《鐐逛俊鎭殑涓�缁存暟缁�
+ private Object[] vertexesArray;
+ //瀛樺偍鍥句腑椤剁偣涔嬮棿鍏宠仈鍏崇郴鐨勪簩缁存暟缁�,鍙婅竟鐨勫叧绯�
+ private int[][] edgesMatrix;
+
+ // 璁板綍绗琲涓妭鐐规槸鍚﹁璁块棶杩�
+ private boolean[] visited;
+
+ /**
+ * @param graphType 鍥剧殑绫诲瀷锛氭湁鍚戝浘/鏃犲悜鍥�
+ * @param method 鍥剧殑瀹炵幇鏂瑰紡锛氶偦鎺ョ煩闃�/閭绘帴琛�
+ */
+ public GraphByMatrix(boolean graphType, boolean method, int size) {
+ this.graphType = graphType;
+ this.method = method;
+ this.vertexSize = 0;
+ this.matrixMaxVertex = size;
+
+ if (this.method) {
+ visited = new boolean[matrixMaxVertex];
+ vertexesArray = new Object[matrixMaxVertex];
+ edgesMatrix = new int[matrixMaxVertex][matrixMaxVertex];
+
+ //瀵规暟缁勮繘琛屽垵濮嬪寲锛岄《鐐归棿娌℃湁杈瑰叧鑱旂殑鍊间负Integer绫诲瀷鐨勬渶澶у��
+ for (int row = 0; row < edgesMatrix.length; row++) {
+ for (int column = 0; column < edgesMatrix.length; column++) {
+ edgesMatrix[row][column] = MAX_VALUE;
+ }
+ }
+
+ }
+ }
+
+ /********************鏈�鐭矾寰�****************************/
+ //璁＄畻涓�涓《鐐瑰埌鍏跺畠涓�涓《鐐圭殑鏈�鐭窛绂�
+ public void Dijkstra(Object obj) throws Exception {
+ Dijkstra(getVertexIndex(obj));
+ }
+ public void Dijkstra(int v0) {
+ int[] dist = new int[matrixMaxVertex];
+ int[] prev = new int[matrixMaxVertex];
+
+ //鍒濆鍖杤isited銆乨ist鍜宲ath
+ for (int i = 0; i < vertexSize; i++) {
+ //涓�寮�濮嬪亣瀹氬彇鐩磋揪璺緞鏈�鐭�
+ dist[i] = edgesMatrix[v0][i];
+ visited[i] = false;
+
+ //鐩磋揪鎯呭喌涓嬬殑鏈�鍚庣粡鐢辩偣灏辨槸鍑哄彂鐐�
+ if (i != v0 && dist[i] < MAX_VALUE)
+ prev[i] = v0;
+ else
+ prev[i] = -1; //鏃犵洿杈捐矾寰�
+ }
+
+ //鍒濆鏃舵簮鐐箆0鈭坴isited闆嗭紝琛ㄧずv0 鍒皏0鐨勬渶鐭矾寰勫凡缁忔壘鍒�
+ visited[v0] = true;
+
+ // 涓嬫潵鍋囪缁忕敱涓�涓偣涓浆鍒拌揪鍏朵綑鍚勭偣,浼氳繎浜�,楠岃瘉涔�
+ // 鍐嶅亣璁剧粡鐢变袱涓偣涓浆,浼氭洿杩戜簺,楠岃瘉涔�,.....
+ // 鐩村埌绌蜂妇瀹屾墍鏈夊彲鑳界殑涓浆鐐�
+ int minDist;
+ int v = 0;
+ for (int i = 1; i < vertexSize; i++) {
+ //鎸戜竴涓窛绂绘渶杩戠粡鐢辩偣,涓嬫爣瑁呭叆 v
+ minDist = MAX_VALUE;
+
+ for (int j = 0; j < vertexSize; j++) {
+ if ((!visited[j]) && dist[j] < minDist) {
+ v = j; // 缁忕敱椤剁偣j涓浆鍒欒窛绂绘洿鐭�
+ minDist = dist[j];
+ }
+ }
+ visited[v] = true;
+
+ /*椤剁偣v骞跺叆S锛岀敱v0鍒拌揪v椤剁偣鐨勬渶鐭矾寰勪负min.
+ 鍋囧畾鐢眝0鍒皏锛屽啀鐢眝鐩磋揪鍏朵綑鍚勭偣锛屾洿鏂板綋鍓嶆渶鍚庝竴涓粡鐢辩偣鍙婅窛绂�*/
+ for (int j = 0; j < vertexSize; j++) {
+ if ((!visited[j]) && edgesMatrix[v][j] < MAX_VALUE) {
+
+ if (minDist + edgesMatrix[v][j] <= dist[j]) {
+ //濡傛灉澶氱粡鐢变竴涓獀鐐瑰埌杈緅鐐圭殑 鏈�鐭矾寰勫弽鑰岃鐭�,灏辨洿鏂�
+ dist[j] = minDist + edgesMatrix[v][j];
+
+ prev[j] = v; //缁忕敱鐐圭殑搴忓彿
+ }
+
+ }
+ }
+
+ }
+
+ for (int i = 1; i < matrixMaxVertex; i++) {
+ System.out.println("**" + vertexesArray[v0] + "-->" +vertexesArray[i] + " 鐨勬渶鐭矾寰勬槸锛�" + dist[i]);
+ }
+ }
+
+ //鑾峰彇椤剁偣鍊煎湪鏁扮粍閲屽搴旂殑绱㈠紩
+ private int getVertexIndex(Object obj) throws Exception {
+ int index = -1;
+ for (int i = 0; i < vertexSize; i++) {
+ if (vertexesArray[i].equals(obj)) {
+ index = i;
+ break;
+ }
+ }
+ if (index == -1) {
+ throw new Exception("娌℃湁杩欎釜鍊硷紒");
+ }
+
+ return index;
+ }
+
+ /**
+ * 鍗曟簮鏈�鐭矾寰勭畻娉曪紝鐢ㄤ簬璁＄畻涓�涓妭鐐瑰埌鍏朵粬!!鎵�鏈夎妭鐐�!!鐨勬渶鐭矾寰�
+ */
+ public void Dijkstra2(int v0) {
+ // LinkedList瀹炵幇浜哘ueue鎺ュ彛 FIFO
+ Queue<Integer> queue = new LinkedList<>();
+ for (int i = 0; i < vertexSize; i++) {
+ visited[i] = false;
+ }
+ List<Map<String,Object>> result = new ArrayList<>();
+ //杩欎釜寰幆鏄负浜嗙‘淇濇瘡涓《鐐归兘琚亶鍘嗗埌
+ int lastRow =0;
+ for (int i = 0; i < vertexSize; i++) {
+ if (!visited[i]) {
+ queue.add(i);
+ visited[i] = true;
+ while (!queue.isEmpty()) {
+ int row = queue.remove();
+ Map<String,Object> map = new HashMap<>();
+ map.put("name", vertexesArray[row]);
+ map.put("row", row);
+ int tempDis =0;
+ if(row>0){
+ tempDis = edgesMatrix[lastRow][row];
+ lastRow =row;
+ }
+ map.put("dis", tempDis);
+ result.add(map);
+ System.out.print(vertexesArray[row] + "-->");
+ for (int k = getMin(row); k >= 0; k = getMin(row)) {
+ if (!visited[k]) {
+ queue.add(k);
+ visited[k] = true;
+ }
+ }
+ }
+ }
+ }
+ System.out.println("");
+ int totalDis =0;
+ for(Map<String,Object> c :result){
+ totalDis += (Integer) c.get("dis");
+ System.out.print( c.get("name") + "--"+c.get("dis")+"-->");
+ }
+ System.out.println("");
+ System.out.println("鏈�鐭窛绂�"+totalDis);
+ }
+
+ private int getMin( int row) {
+ int minDist = MAX_VALUE;
+ int index = 0;
+ for (int j = 0; j < vertexSize; j++) {
+ if ((!visited[j]) && edgesMatrix[row][j] < minDist) {
+ minDist = edgesMatrix[row][j];
+ index = j;
+ }
+ }
+ if (index == 0) {
+ return -1;
+ }
+ return index;
+ }
+
+ public boolean addVertex(Object val) {
+ assert (val != null);
+ vertexesArray[vertexSize] = val;
+ vertexSize++;
+ return true;
+ }
+
+ public boolean addEdge(int vnum1, int vnum2, int weight) {
+ assert (vnum1 >= 0 && vnum2 >= 0 && vnum1 != vnum2 && weight >= 0);
+
+ //鏈夊悜鍥�
+ if (graphType) {
+ edgesMatrix[vnum1][vnum2] = weight;
+
+ } else {
+ edgesMatrix[vnum1][vnum2] = weight;
+ edgesMatrix[vnum2][vnum1] = weight;
+ }
+
+ return true;
+ }
+
+ public static void main(String[] args) throws Exception {
+ GraphByMatrix graph = new GraphByMatrix(GraphByMatrix.DIRECTED_GRAPH, GraphByMatrix.ADJACENCY_MATRIX, 9);
+
+ graph.addVertex("A");//0
+ graph.addVertex("B");//1
+ graph.addVertex("C");//2
+ graph.addVertex("D");//3
+ graph.addVertex("E");//4
+
+ //A->B銆丆銆丏
+ graph.addEdge(0, 1,10);
+ graph.addEdge(0, 2,5);
+ graph.addEdge(0, 3,7);
+ //B->C銆丏銆丒
+ graph.addEdge(1, 2,4);
+ graph.addEdge(1, 3,5);
+ graph.addEdge(1, 4,10);
+ //C->B銆丏銆丒
+ graph.addEdge(2, 1,4);
+ graph.addEdge(2, 3,6);
+ graph.addEdge(2, 4,5);
+ //D->B銆丆銆丒
+ graph.addEdge(3, 1,5);
+ graph.addEdge(3, 2,6);
+ graph.addEdge(3, 4,7);
+
+
+ graph.Dijkstra(0);
+ System.out.println();
+ graph.Dijkstra("C");
+ System.out.println();
+ graph.Dijkstra2(0);
+ System.out.println();
+ }
+
+}
\ No newline at end of file
--
Gitblit v1.9.3