java实现dijkstra

Ⅰ 我正在学习数据结构，但是我发现有些算法例如dijkstra虽然明白大概怎么回事，但是就是用java语言实现不了

这个，数据结构其实很多时候只限于八种排序算法，哥儿们，有一本专门的JAVA数据结构，你可以去看看，先把什么递归排序呀，哈希什么的搞完，就差不多了，迪科斯彻算法我也不是很了解，有空一起搞一下，嘻嘻，祝你NB

Ⅱ 矩阵怎么用来计算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中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));

}
}

Ⅳ 图遍历算法之最短路径Dijkstra算法

最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：

常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。

Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决着名的旅行商问题。

问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。

为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。

以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：

注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进

第2步 ：选取顶点 添加进 ，更新 中顶点最短距离

第3步 ：选取顶点 添加进 ，更新 中顶点最短距离

第4步 ：选取顶点 添加进 ，更新 中顶点最短距离

第5步 ：选取顶点 添加进 ，更新 中顶点最短距离

第6步 ：选取顶点 添加进 ，更新 中顶点最短距离

第7步 ：选取顶点 添加进 ，更新 中顶点最短距离

示例：node编号1-7分别代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))输出结果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))输出结果：

示例：

找到D（4）到G（7）的最短路径：

[1] 维基网络，最短路径问题： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

Ⅳ 寻求大神帮忙写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怎么用迪杰斯特拉算有向图有权值的最短路径

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算法实现。

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帮我实现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")

Ⅸ dijkstra的优化可以用数组+优先队列吗

基于java类库的PriorityQueue的PriorityQueue+Dijkstra实现：

[java]view plain

• importjava.util.HashMap;

• importjava.util.HashSet;

• importjava.util.Iterator;

• importjava.util.PriorityQueue;

• importjava.util.Scanner;

• importjava.util.Set;

• /**

• *PriorityQueue+Dijkstra算法求单源最短路径

• *首推此方法

• *虽然优先级队列优化比堆优化性能差一点，差距很小。

• *但是优先级队列可以直接使用java类库中的PriorityQueue来实现，

• *而堆优化实现非常复杂。

• *

• *@authorDuXiangYu

• *

• */

• publicclassDijKstra_link_Queue{

• staticintnodeCount;

• staticintedgeCount;

• //邻接表表头数组

• staticNode[]firstArray;

• //最短路径数组

• //staticint[]dist;

• //S集合,代表着已经找到最短路径的结点

• staticHashSet<Integer>s;

• //映射集合

• staticdist[]distArray;

• //优先级队列

• staticPriorityQueue<dist>pq;

• staticintmax=1000000;

• /**

• *结点类

• *

• *@authorDuXiangYu

• */

• staticclassNode{

• //邻接顶点map

• privateHashMap<Integer,Integer>map=null;

• publicvoidaddEdge(intend,intedge){

• if(this.map==null){

• this.map=newHashMap<Integer,Integer>();

• }

• this.map.put(end,edge);

• }

• }

• /**

• *dist:保存源结点至每个结点的最短路径

• *@authorDuXiangYu

• *

• */

• <dist>{

• intvalue;

• intindex;

• publicdist(intvalue,intindex){

• this.value=value;

• this.index=index;

• }

• @Override

• publicintcompareTo(disto){

• if(o.value<this.value){

• return1;

• }elseif(o.value>this.value){

• return-1;

• }else{

• return0;

• }

• }

• }

• publicstaticvoidmain(String[]args){

• Scannersc=newScanner(System.in);

• nodeCount=sc.nextInt();

• edgeCount=sc.nextInt();

• firstArray=newNode[nodeCount+1];

• for(inti=0;i<nodeCount+1;i++){

• firstArray[i]=newNode();

• }

• for(inti=0;i<edgeCount;i++){

• intbegin=sc.nextInt();

• intend=sc.nextInt();

• intedge=sc.nextInt();

• firstArray[begin].addEdge(end,edge);

• }

• sc.close();

• longbegin=System.currentTimeMillis();

• djst();

• longend=System.currentTimeMillis();

• System.out.println(end-begin+"ms");

• }

• /**

• *PriorityQueue+Dijkstra算法实现

• */

• privatestaticvoiddjst(){

• s=newHashSet<Integer>();

• pq=newPriorityQueue<dist>(nodeCount);

• distArray=newdist[nodeCount+1];

• NodetempNode=firstArray[1];

• for(inti=2;i<nodeCount+1;i++){

• HashMap<Integer,Integer>tempMap=tempNode.map;

• if(tempMap.containsKey(i)){

• distd=newdist(tempMap.get(i),i);

• pq.offer(d);

• distArray[i]=d;

• }else{

• distd=newdist(max,i);

• pq.offer(d);

• distArray[i]=d;

• }

• }

• s.add(1);

• while(s.size()<nodeCount){

• distd=pq.poll();

• intindex=d.index;

• intvalue=d.value;

• s.add(index);

• //用indx这个点去更新它的邻接点到开始点的距离

• HashMap<Integer,Integer>m=firstArray[index].map;

• if(m==null){

• continue;

• }

• Set<Integer>set=m.keySet();

• Iterator<Integer>it=set.iterator();

• while(it.hasNext()){

• intnum=it.next();

• if(num==1){

• continue;

• }

• disttempDist=distArray[num];

• if(m.get(num)+value<tempDist.value){

• pq.remove(tempDist);

• tempDist.value=m.get(num)+value;

• pq.offer(tempDist);

• distArray[num]=tempDist;

• }

• }

• }

• for(inti=2;i<nodeCount+1;i++){

• System.out.println(distArray[i].value);

• }

• }

• }</span></span>