您的位置:

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

本文目录一览:

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:许多点构成许多路径,从中找出两点间的最短路径,怎么实现?

可以通过循环查找,然后比较两点的距离,建立一个局部变量来获取这个比较后的短的距离,最终得到的就是这许多路径的最短路径