圖的最短路徑java

發布時間: 2023-06-09 12:20:05

『壹』用java怎麼用迪傑斯特拉算有向圖有權值的最短路徑

Dijkstra(迪傑斯特拉)演算法是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其採用的是貪心法的演算法策略，大概過程如下：
1.聲明兩個集合，open和close，open用於存儲未遍歷的節點，close用來存儲已遍歷的節點
2.初始階段，將初始節點放入close，其他所有節點放入open
3.以初始節點為中心向外一層層遍歷，獲取離指定節點最近的子節點放入close並從新計算路徑，直至close包含所有子節點

代碼實例如下：
Node對象用於封裝節點信息，包括名字和子節點
[java] view plain
public class Node {
private String name;
private Map<Node,Integer> child=new HashMap<Node,Integer>();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<Node, Integer> getChild() {
return child;
}
public void setChild(Map<Node, Integer> child) {
this.child = child;
}
}

MapBuilder用於初始化數據源，返回圖的起始節點
[java] view plain
public class MapBuilder {
public Node build(Set<Node> open, Set<Node> close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
圖的結構如下圖所示：

Dijkstra對象用於計算起始節點到所有其他節點的最短路徑
[java] view plain
public class Dijkstra {
Set<Node> open=new HashSet<Node>();
Set<Node> close=new HashSet<Node>();
Map<String,Integer> path=new HashMap<String,Integer>();//封裝路徑距離
Map<String,String> pathInfo=new HashMap<String,String>();//封裝路徑信息
public Node init(){
//初始路徑,因沒有A->E這條路徑,所以path(E)設置為Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A->B");
path.put("C", 1);
pathInfo.put("C", "A->C");
path.put("D", 4);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A->F");
path.put("G", 5);
pathInfo.put("G", "A->G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//將初始節點放入close,其他節點放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距離start節點最近的子節點,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
Map<Node,Integer> childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子節點在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())>newCompute){//之前設置的距離大於新計算出來的距離
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
}
}
}
computePath(start);//重復執行自己,確保所有子節點被遍歷
computePath(nearest);//向外一層層遞歸,直至所有頂點被遍歷
}
public void printPathInfo(){
Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
for(Map.Entry<String, String> pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 獲取與node最近的子節點
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
Map<Node,Integer> childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distance<minDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}

Main用於測試Dijkstra對象
[java] view plain
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}

『貳』 JAVA求10個景點間各個景點的最短路徑圖隨便話距離隨便求代碼

最有效，切不復雜的方法使用Breadth First Search (BFS). 基本代碼如下（偽代碼）。因為BFS不用遞歸，所以可能會有點難理解。

public Stack findPath(Vertex 起始景點, Vertex 目標景點){
Queue <Vertex> q = new Queue<Vertex>();
s.enqueue(起始景點);
Vertex 當前位置;
while(!s.isEmpty()){
當前位置 = s.dequeue();
if (當前位置 == 目標景點) break;
for (每一個相鄰於當前位置的景點 Vertex v){
if (!v.visited){
v.parent = 當前位置;
// 不是規定，不過可以節省一點時間
if (v == 目標景點){
current = v;
break;
}
s.enqueue(Vertex v);
v.visited = true;
}
}
}

Stack <Vertex> solution = new Stack <Vertex>();
Vertex parent = current;
while (parent != 起始景點){
solution.push(parent);
parent = current.parent;
}

for (graph中的每一個vertex) vertex.visited = false;

return solution(); // 其實這里建議用一個 Path 的inner class 來裝所獲得的路線
}

然後再 main 求每兩個景點之間的距離即可
public static void main(String[] argv){
PathFinder pf = new PathFinder();

Stack[][] 路徑 = new Stack[10][10];

for(int i=0; i<pf.vertices.length; i++){
for(int j=i+1; j<pf.vertices.length; j++){
Stack s = pf.findPath(pf.vertices[i], pf.vertices[j]);
路徑[i][j] = s; 路徑[j][i] = s; // 假設你的graph是一個undirected graph

}

}

// 這么一來就大功告成了！對於每兩個景點n 與 m之間的最短路徑就是在 stack[n][m] 中

}

還有一種方法就是用Depth First Search遞歸式的尋找路徑，不過這樣比較慢，而且我的代碼可能會造成stack overflow

public Stack dfs(Vertex 當前景點，Vertex 目標景點){
if(當前景點 == 目標景點) return;

Stack solution = new Stack();
Stack temp;
for (相鄰於點錢景點的每一個 Vertex v){
if (!v.visited){
v.visited = true;
temp = dfs(v, 目標景點);
// 抱歉，不記得是stack.size()還是stack.length()

if (solution.size() == 0) solution = temp;
else if(temp.size() < solution.size()) solution = temp;

v.visited = false; 復原

}

}

return solution;

}
然後再在上述的Main中叫dfs...

參考：
http://www.cs.berkeley.e/~jrs/61b/lec/29
http://www.cs.berkeley.e/~jrs/61b/lec/28

『叄』請教JAVA實現GIS最短路徑輸出

而輸出最短路徑的時候，在網上也進行了查閱，沒發現什麼標準的方法，於是在下面的實現中，我給出了一種能夠想到的比較精簡的方式：利用prev[]數組進行遞歸輸出。

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

package graph.dijsktra;

import graph.model.Point;

import java.util.*;

/**
* Created by MHX on 2017/9/13.
*/
public class Dijkstra {
private int[][] map; // 地圖結構保存
private int[][] edges; // 鄰接矩陣
private int[] prev; // 前驅節點標號
private boolean[] s; // S集合中存放到起點已經算出最短路徑的點
private int[] dist; // dist[i]表示起點到第i個節點的最短路徑
private int pointNum; // 點的個數
private Map<Integer, Point> indexPointMap; // 標號和點的對應關系
private Map<Point, Integer> pointIndexMap; // 點和標號的對應關系
private int v0; // 起點標號
private Point startPoint; // 起點
private Point endPoint; // 終點
private Map<Point, Point> pointPointMap; // 保存點和權重的映射關系
private List<Point> allPoints; // 保存所有點
private int maxX; // x坐標的最大值
private int maxY; // y坐標的最大值

public Dijkstra(int map[][], Point startPoint, Point endPoint) {
this.maxX = map.length;
this.maxY = map[0].length;
this.pointNum = maxX * maxY;
this.map = map;
this.startPoint = startPoint;
this.endPoint = endPoint;
init();
dijkstra();
}

『肆』求java代碼，關於帶權有向圖找最短距離，數據結構方面

so..................復雜

『伍』求java實現矩陣圖上任意兩點的最短路徑源碼

我用的是遞歸調用方法，有個小問題就是在列印步數的時候是返向的，原因是就是程序不斷的調用自己，到最後判斷基值位準退出調用。這才開始從棧里取出方法進行執行的原因。

代碼欣賞：

publicstaticintstep=1;

=newStringBuffer();

publicstaticint[][]maze={{1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,1,0,0,0,0,0,1},

{1,0,1,0,0,0,1,0,1,1,1},

{1,0,0,0,1,0,1,0,0,0,1},

{1,0,1,1,0,0,1,0,0,1,1},//0代表可以通過，1代表不可通過

{1,0,1,0,1,1,0,1,0,0,1},

{1,0,0,0,0,0,0,0,1,0,1},

{1,0,1,0,1,0,1,0,1,0,1},

{1,0,0,1,0,0,1,0,1,0,1},

{1,1,1,1,1,1,1,1,1,1,1}};

publicstaticvoidmain(String[]args){

inti,j;//循環記數變數

Sample.way(1,1);//二維數組起始值從下標1，1開始

System.out.println("起點從坐標x=1,y=1開始");

System.out.println("終點坐標是x=8,y=9結束");

System.out.println("這是迷宮圖表");

System.out.println("012345678910");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

for(i=0;i<10;i++){

System.out.print(""+i+"‖");

for(j=0;j<11;j++)

System.out.print("-"+maze[i][j]+"-‖");

System.out.println("");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

}

//列印顯示步數

System.out.print(printStep.toString());

}

publicstaticbooleanway(intx,inty){

if(maze[8][9]==2)//代表遞歸終止條件（也就是當走出出口時標記為2）

returntrue;

else{

if(maze[y][x]==0){

maze[y][x]=2;

*下面if判斷條件代表當前坐標為基點，

*根據判斷對當前位置進行遞歸調用：如：

*往上、往右上、往右、往右下、往下、

*往左下、往左、往左上的坐標是否可走，

*判斷是否可走的返回條件是：

*2代表可通過、1代表不能通過、3表示已經走過，但是未能走通。

if(way(x,y-1)){