dijkstra算法java代码_寻求大神帮忙写Java代码要用Dijkstra’s algorithm（迪杰斯特拉算法）

① 迪杰斯特拉算法问题，求pascal代码详解，有重赏！

② java如何实现深度优先广度优先

下面是我修改了滴源码，是基于一张简单的地图，在地图上搜索目的节点，依次用深度优先、广度优先、Dijkstra算法实现。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Stack;

/**
*
* @author yinzhuo
*
*/
public class Arithmatic {
boolean flag = true;
// 一张地图
static int[][] map = new int[][]// 地图数组
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

③ 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

④ 矩阵怎么用来计算dijkstra算法 java

怎样用matlab编程实现Dijkstra算法
%单源点最短路径Dijkstra算法实现

function [d index1 index2] = Dijkf(a)

% a 表示图的权值矩阵

% d 表示所求最短路的权和

% index1 表示标号顶点顺序

% index2 表示标号顶点索引

%参数初始化

M= max(max(a));

pb(1:length(a))= 0; % 标记向量,表明是否已进入S集合

pb(1)= 1;

index1= 1;

index2= ones(1,length(a));

d(1:length(a))= M; % d矩阵所有元素都初始化为最大权值

d(1)= 0; % 以v1点为源点

temp= 1;

% 更新l(v),同时记录顶点顺序和顶点索引

while sum(pb)<length(a) % 重复步骤2,直到满足停止条件

tb= find(pb==0);

d(tb)= min(d(tb),d(temp)+a(temp,tb)); % 更新l(v)

tmpb= find(d(tb)==min(d(tb))); % 找出min(l(v))

temp= tb(tmpb(1));

pb(temp)= 1;

index1= [index1,temp]; % 记录标号顺序

index= index1(find(d(index1)==d(temp)-a(temp,index1)));

if length(index)>=2

index= index(1);

end % if结束

index2(temp)= index; % 记录标号索引

end % while结束

end

% Dijkf函数结束

⑤ 用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代码，要用Dijkstra’s algorithm（迪杰斯特拉算法）

package minRoad.no;

import java.util.Arrays;

//这个程序用来求得一个图的最短路径矩阵
public class ShortestDistance_V4 {
private static final int inf = Integer.MAX_VALUE;// 表示两个点之间无法直接连通

public static int[][] dijkstra(int[][] graph) {
int min, v, u = 0, n = graph.length;
int[] path = new int[n];
int[] dist = new int[n];
boolean[] s = new boolean[n];
Arrays.fill(s, false);
Arrays.fill(dist, inf);
for (int i = 0; i < n; i++) {
dist[i] = graph[u][i];
if (i != u && dist[i] < inf)
path[i] = u;
else
path[i] = -1;
}
s[u] = true;
while (true) {
min = inf;
v = -1;
// 找到最小的dist
for (int i = 0; i < n; i++) {
if (!s[i]) {
if (dist[i] < min) {
min = dist[i];
v = i;
}
}
}
if (v == -1) break;// 找不到更短的路径了
// 更新最短路径
s[v] = true;
for (int i = 0; i < n; i++) {
if (!s[i] && graph[v][i] != inf && dist[v] + graph[v][i] < dist[i]) {
dist[i] = dist[v] + graph[v][i];
path[i] = v;
}
}
}
// 输出路径
int[] shortest = new int[n];
for (int i = 1; i < n; i++) {
Arrays.fill(shortest, 0);
int k = 0;
shortest[k] = i;
while (path[shortest[k]] != 0) {
k++;
shortest[k] = path[shortest[k - 1]];
}
k++;
shortest[k] = 0;
}
int[] tmp = new int[shortest.length];
for (int i = 0; i < tmp.length; i++) {
tmp[i] = shortest[tmp.length - i - 1];
}
return new int[][] { dist, tmp };
}

/**
* <pre>
* v0
* 1, v1
* 4, 2, v2
* inf, 7, -1, v3
* inf, 5, 1, 3, v4
* inf, inf, inf, 2, 6, v5
* </pre>
*
* *
*
* <pre>
* A--------30------->D
* |\ ∧|
* | \ / |
* | \ / |
* | 10 10 |
* | \ / 20
* | \ / |
* | \ / |
* | ∨ / ∨
* 20 B E
* | / ∧
* | / /
* | / /
* | 5 /
* | / 30
* | / /
* | / /
* ∨∠ /
* C
* </pre>
*
* @param args
*/
public static void main(String[] args) {
int[][] W1 = {
{ 0, 10, 20, 30, inf },
{ 10, 0, 5, 10, inf },
{ 20, 5, 0, inf, 30 },
{ 30, 10, inf, 0, 20 },
{ inf, inf, 30, 20, 0 },
};
// http://sbp810050504.blog.51cto.com/2799422/690803
// http://sbp810050504.blog.51cto.com/2799422/1163565
// int[][] W = {
// { 0, 1, 4, inf, inf, inf },
// { 1, 0, 2, 7, 5, inf },
// { 4, 2, 0, inf, 1, inf },
// { inf, 7, inf, 0, 3, 2 },
// { inf, 5, 1, 3, 0, 6 },
// { inf, inf, inf, 2, 6, 0 }};
int[][] distAndShort = dijkstra(W1);
System.out.println(Arrays.toString(distAndShort[0]));
System.out.println(Arrays.toString(distAndShort[1]));
// distance: { 0, 1, 3, 7, 4, 9};
}
}

⑦ 跪求解释java中shortestpath.DijkstraDistance的具体用法

//这个算法用来解决无向图中任意两点的最短路径
_V5{
publicstaticintdijkstra(int[][]W1,intstart,intend){
boolean[]isLabel=newboolean[W1[0].length];//是否标号
int[]indexs=newint[W1[0].length];//所有标号的点的下标集合，以标号的先后顺序进行存储，实际上是一个以数组表示的栈
inti_count=-1;//栈的顶点
int[]distance=W1[start].clone();//v0到各点的最短距离的初始值
intindex=start;//从初始点开始
intpresentShortest=0;//当前临时最短距离

indexs[++i_count]=index;//把已经标号的下标存入下标集中
isLabel[index]=true;

while(i_count<W1[0].length){
//第一步：标号v0,即w[0][0]找到距离v0最近的点

intmin=Integer.MAX_VALUE;
for(inti=0;i<distance.length;i++){
if(!isLabel[i]&&distance[i]!=-1&&i!=index){
//如果到这个点有边,并且没有被标号
if(distance[i]<min){
min=distance[i];
index=i;//把下标改为当前下标
}
}
}
if(index==end){//已经找到当前点了，就结束程序
break;
}
isLabel[index]=true;//对点进行标号
indexs[++i_count]=index;//把已经标号的下标存入下标集中
if(W1[indexs[i_count-1]][index]==-1
||presentShortest+W1[indexs[i_count-1]][index]>distance[index]){
//如果两个点没有直接相连，或者两个点的路径大于最短路径
presentShortest=distance[index];
}else{
presentShortest+=W1[indexs[i_count-1]][index];
}

//第二步：将distance中的距离加入vi
for(inti=0;i<distance.length;i++){
//如果vi到那个点有边，则v0到后面点的距离加
if(distance[i]==-1&&W1[index][i]!=-1){//如果以前不可达，则现在可达了
distance[i]=presentShortest+W1[index][i];
}elseif(W1[index][i]!=-1
&&presentShortest+W1[index][i]<distance[i]){
//如果以前可达，但现在的路径比以前更短，则更换成更短的路径
distance[i]=presentShortest+W1[index][i];
}

}
}
//如果全部点都遍历完，则distance中存储的是开始点到各个点的最短路径
returndistance[end]-distance[start];
}
publicstaticvoidmain(String[]args){
//建立一个权值矩阵
int[][]W1={//测试数据1
{0,1,4,-1,-1,-1},
{1,0,2,7,5,-1},
{4,2,0,-1,1,-1},
{-1,7,-1,0,3,2},
{-1,5,1,3,0,6},
{-1,-1,-1,2,6,0}};
int[][]W={//测试数据2
{0,1,3,4},
{1,0,2,-1},
{3,2,0,5},
{4,-1,5,0}};

System.out.println(dijkstra(W1,0,4));

}
}

⑧ 求大佬用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")

⑨ 求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)){