java最短路徑,求最短路徑的方法

本文目錄一覽：

• 1、JAVA求10個景點間各個景點的最短路徑 圖隨便話 距離隨便 求代碼
• 2、用java語言求最短路徑
• 3、Java最短路徑應用程序
• 4、JAVA中最短路徑演算法
• 5、Java/Android：許多點構成許多路徑，從中找出兩點間的最短路徑，怎麼實現？

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

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

public Stack findPath(Vertex 起始景點, Vertex 目標景點){

Queue Vertex q = new QueueVertex();

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; ipf.vertices.length; i++){

for(int j=i+1; jpf.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…

參考：

用java語言求最短路徑

最短路徑就是敲代碼。 這個東西行業公認,沒有比敲代碼學語言更加快的路了。

如果是單純感興趣可以買兩本書自學 什麼thinkinjava之類的，開始肯定看不懂的,誰開始都看不懂,摸索著來,時間長了就理解了。如果有其它語言基礎學起來就快多了,因為語言這種東西,除了語法不一樣,邏輯都是一樣的。

如果是工作需要什麼的,可以找個培訓啥的。當然前提你有錢。

最後順帶吐個槽,捷徑好找的話，程序員這工作就不值錢了。

Java最短路徑應用程序

package Test3;

import java.util.LinkedList;

import java.util.List;

/**

* 單源最短路徑問題

*

* @author Sailor

*

*/

public class ShortestPath {

private static String showPath[] = { “”, “”, “”, “”, “”, “” };

// 返回圖的最短路徑

public static int[] getShortPath(int path[][]) {

LinkedListInteger savePath = new LinkedListInteger();// 用於保存已添加進來的節點

int mark = 1;

int shortestPath[] = new int[path.length];

for (int i = 0; i shortestPath.length; i++) {

shortestPath[i] = -1;

}

savePath.add(new Integer(0));

if (savePath.size() == 1) {

int num = savePath.getLast().intValue();

int minIndex = 0;

for (int j = 0; j shortestPath.length; j++) {

shortestPath[j] = path[num][j];

if (shortestPath[j] = 0) {

showPath[j] = “1–” + (j + 1);

} else {

showPath[j] = “無通路”;

}

}

minIndex = getAddIndex(savePath, shortestPath);

savePath.add(minIndex);

}

if (savePath.size() 1) {

while (mark 6) {// savePath.size()6 當有不可到達的點是將要出現死循環

int num = savePath.getLast().intValue();

int minIndex = 0;

for (int j = 0; j path.length; j++) {

if (path[num][j] = 0) {

if (shortestPath[j] 0) {

shortestPath[j] = path[num][j] + shortestPath[num];

showPath[j] = showPath[num] + “–” + (j + 1);

} else {

if (shortestPath[num] + path[num][j] shortestPath[j]) {

shortestPath[j] = shortestPath[num]

+ path[num][j];

showPath[j] = showPath[num] + “–” + (j + 1);

}

}

}

}

minIndex = getAddIndex(savePath, shortestPath);

if (minIndex 0)

savePath.add(minIndex);

mark++;

}

}

return shortestPath;

}

// 獲得加入到保存路徑的節點

public static int getAddIndex(List list, int num[]) {

int index = 0;

for (int i = 0; i num.length; i++) {

if (!list.contains(new Integer(i))) {

if (num[i] 0 index == 0) {

index = i;

}

if (num[i] 0 index 0) {

if (num[i] num[index])

index = i;

}

}

}

return index;

}

public static void main(String[] args) {

int path[][] = { { 0, -1, 15, -1, -1, -1 }, { 2, 0, -1, -1, 10, 30 },

{ -1, 4, 0, -1, -1, 10 }, { -1, -1, -1, 0, -1, -1 },

{ -1, -1, -1, 15, 0, -1 }, { -1, -1, -1, 4, 10, 0 } };

int shortestPaht[] = getShortPath(path);

for (int i = 0; i shortestPaht.length; i++) {

System.out.print(“節點 1 到節點 ” + (i + 1) + ” 的最短距離是”

+ shortestPaht[i] + “\t”);

System.out.println(“路徑為：” + showPath[i]);

}

}

}

這是最短路徑的演算法

你再加個畫圖功能就行咧

JAVA中最短路徑演算法

給你個算graph上最短路徑的比較流行的方法

Algorithm Dijkstra(V, E, cost, s)

T ;

Cost(V[s]) 0

Prev(V[s]) none

for i 0 to length[V] – 1 do

if (i 6= s) then

Cost(V[i]) +1

Prev(V[i]) none

Build heap NotInTree from V

for i 1 to length[V] do

u DeleteMin(NotInTree)

add (u, Prev(u)) to T

for each neighbor v of u do

if (Cost(v) Cost(u) + cost(u,v)) then

Cost(v) Cost(u) + cost(u,v)

Prev(v) u

return T

Java/Android：許多點構成許多路徑，從中找出兩點間的最短路徑，怎麼實現？

可以通過循環查找，然後比較兩點的距離，建立一個局部變數來獲取這個比較後的短的距離，最終得到的就是這許多路徑的最短路徑