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>