dijkstra算法代码java

Ⅰ 求！最短路径算法 Dijkstra 用C语言编出来

Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪

/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图，有一个特异的顶点s称为缘。
单源最短路径问题，或者称为最短路径问题，是要确定从s到V中没一个其他
顶点的距离，这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给我了c++下的源代码！ --by 伟伟猪
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;}
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/

Ⅱ 看到你给别人回答的哪个用java编dijkstra的算法，我也想咨询你一下

朋友加油好

Ⅲ 矩阵怎么用来计算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’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};
}
}

Ⅳ 求Dijkstra算法的源代码

Dijkstra算法--c++源代码--

#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;}
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/

Ⅵ 关于最短路的Dijkstra算法的程序源代码!

function [l,z]=Dijkstra(W)
n = size (W,1);
for i = 1 :n
l(i)=W(1,i);
z(i)=1;
end
i=1;
while i<=n
for j =1 :n
if l(i)>l(j)+W(j,i)
l(i)=l(j)+W(j,i);
z(i)=j;

if j<i
if j~=1
i=j-1;
else
i=1;
end
end
end
i=i+1;
end
% W =[ 0 2 1 8 Inf Inf Inf Inf
% 2 0 Inf 6 1 Inf Inf Inf
% 1 Inf 0 7 Inf Inf 9 Inf
% 8 6 7 0 5 1 2 Inf
% Inf 1 Inf 5 0 3 Inf 9
% Inf Inf Inf 1 3 0 4 6
% Inf Inf 9 2 Inf 4 0 3
% Inf Inf Inf Inf 9 6 3 0 ];

得到实验数据结果：

L： 0 2 1 7 3 6 9 12

Z： 1 1 1 6 2 5 4 5

其中L为从1出发的结点到其他各个结点的路径长度，Z为路径上的结点，具体路径可由如下方法获得：

如查看1号到4号结点的路径，要经过6号1——》6——》4，而1号到6号要经过5号，即1——》5——》6——》4，进一步1号到5号要经过2号，即1——》2——》5——》6——》4，最后，因为1号可以直接到2号，故最短路径确定为1——》2——》5——》6——》4。

这里面加入了if j<i，因为在每次i循环时，i代表的是目的结点，j代表的是通过结点j到达目标结点i，就是说如果当i为5时表示到前几个目标结点的最短路径已经确定了，但是如果此时发现经过的结点j《i产生了新的最短路径，则需要重新确定结点j为目标时的最短路径。

另附一个对比算法：

用于求从起始点s到其它各点的最短路
%D为赋权邻接矩阵，d为s到其它各点最短路径的长度，DD记载了最短路径生成树
function [d,DD]=dijkstra_aiwa(D,s)
[m,n]=size(D);
d=inf.*ones(1,m);
d(1,s)=0;
dd=zeros(1,m);
dd(1,s)=1;
y=s;
DD=zeros(m,m);
DD(y,y)=1;
counter=1;
while length(find(dd==1))<m
for i=1:m
if dd(i)==0
d(i)=min(d(i),d(y)+D(y,i));
end
end
ddd=inf;
for i=1:m
if dd(i)==0&&d(i)<ddd
ddd=d(i);
end
end
yy=find(d==ddd);
counter=counter+1;
DD(y,yy(1,1))=counter;
DD(yy(1,1),y)=counter;
y=yy(1,1);
dd(1,y)=1;
end

Ⅶ 用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();
}
}

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

packageminRoad.no;importjava.util.Arrays;//这个程序用来求得一个图的最短路径矩阵publicclassShortestDistance_V4{privatestaticfinalintinf=Integer.MAX_VALUE;//表示两个点之间无法直接连通publicstaticint[][]dijkstra(int[][]graph){intmin,v,u=0,n=graph.length;int[]path=newint[n];int[]dist=newint[n];boolean[]s=newboolean[n];Arrays.fill(s,false);Arrays.fill(dist,inf);for(inti=0;i******A--------30------->D*|\∧|*|\/|*|\/|*|1010|*|\/20*|\/|*|\/|*|∨/∨*20BE*|/∧*|//*|//*|5/*|/30*|//*|//*∨∠/*C***@paramargs*/publicstaticvoidmain(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},};///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代码，关于带权有向图找最短距离，数据结构方面

so..................复杂

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