最短路徑演算法java

發布時間: 2022-06-30 03:09:43

1. 求最短路徑演算法

java">importjava.awt.*;
importjava.util.HashSet;
importjava.util.Random;

classexample2{


privatestaticPoint[]mTestPoints;

//已知平面上N點坐標,求遍歷所有點的最短路徑.
publicstaticvoidmain(String[]args){

//兩點之間的距離d=√(a^2+b^2)其中a=|x1–x2|;b=|y1-y2|
//都是簡單的正相關函數,距離最短那麼需要a+b最小
//n個點需要求C(n,2)次
//其實java提供了兩點之間距離的Api咱們直接使用即可

generateTestPoints();

doubleminDistance=Double.MAX_VALUE;
for(inti=0;i<mTestPoints.length;i++){
//兩兩計算,數組中每個點只跟後面的點求距離
for(intj=i+1;j<mTestPoints.length;j++){
doubledistance=mTestPoints[i].distance(mTestPoints[j]);
if(distance<minDistance){
minDistance=distance;
}
}
}
//得到結果
System.out.println("最短距離為:"+minDistance);
}

(){

//隨機生成10個點的集合,為了去重使用hashSet
Randomrandom=newRandom();
HashSet<Point>mPointSet=newHashSet<>();
for(inti=0;i<10;i++){
booleanadd=mPointSet.add(newPoint(random.nextInt(100),random.nextInt(100)));
if(!add){
--i;
}
}
mTestPoints=mPointSet.toArray(newPoint[10]);
}
}

2. 求大佬用java幫我實現dijkstra演算法，單源最短路徑

python">import heapq
from collections import defaultdict
edges = [["A","B"],["A","D"],["A","E"],["B","C"],["C","E"],["D","E"],["D","C"]]
dist = [10,30,100,50,10,60,20]
res = []
def dijkstra(e,dist,start,end):
‍  hm = defaultdict(list)
‍  for i in range(len(e)):
‍  ‍  hm[e[i][0]].append((e[i][1],dist[i]))
‍  r = {}
‍  r[start] = 0
‍  q = [(0,start,[start])]
‍  while q:
‍  ‍  dis,node,res = heapq.heappop(q)
‍  ‍  if node == end:
‍  ‍  ‍  return dis,res
‍  ‍  for u,v in hm[node]:
‍  ‍  ‍  t = dis+v
‍  ‍  ‍  if u not in r or t < r[u]:
‍  ‍  ‍  ‍  r[u] = t
‍  ‍  ‍  ‍  heapq.heappush(q,(t,u,res+[u]))
‍  return 0,[]
dijkstra(edges,dist,"A","E")

3. 有什麼無權無向圖的最短路徑演算法比較好，求一個用java實現的

有什麼無權無向圖的最短路徑演算法比較好

帶權圖也分有向和無向兩種，基本的演算法可以看看書咯。帶權的無向圖的最短路徑又叫最小生成樹，Prim演算法和Kruskal演算法；帶權的有向圖的最短路徑演算法有迪傑斯特拉演算法和佛洛依德演算法；

String[]s={"January","February","March","April","May","June","July","August","September","October","November","December"};
System.out.print("請輸入數字（1-12）：");
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
Stringstr=br.readLine();
intm=Integer.parseInt(str);
if(m<=0||m>=13)
{

4. java，最短路徑問題

這個的東西已經忘記了。記得是學離散數學的時候有講過，lz還是自己去找本專業書看看吧

5. Java 最短路徑演算法如何實現有向任意兩點的最短路徑

http://blog.csdn.net/javaman_chen/article/details/8254309

6. 如何求解最短路徑（求Java程序實現）

那你就別弄最短的。你把所有的路徑都查出來。然後比較長短，然後從短到長依次列印出來不就行了嘛。。

7. 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

8. 一批貨物准備從A地到E地，有如下可能的路線提供選擇：（最短路徑問題），求演算法設計，用java或者C語言

//定義結構節點
struct Node
{
std::string Name; //編號
std::list<Node*> Branch;//從該點可走的分支
}
//邏輯流程
1，初始化所有節點數據，定義開始和結束的點
2，從開始節點開始生成移動的樹
3，第一次出現終點的層數就是最短路徑長度

細節自己琢磨一下咯

9. 求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)){