迪傑斯特拉演算法java

1. 圖遍歷演算法之最短路徑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/

2. dijkstra演算法是什麼

迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。

對於圖G=（V，E），將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為｛v0}）。第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。

堆優化

思考

該演算法復雜度為n^2,我們可以發現，如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的復雜度降為O(1)；每次調整的復雜度降為O（elogn）；e為該點的邊數，所以復雜度降為O((m+n)logn)。

實現

1、將源點加入堆，並調整堆。

2、選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。

3、處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點

1):若該點在堆里，更新距離，並調整該元素在堆中的位置。

2):若該點不在堆里，加入堆，更新堆。

4、若取到的u為終點，結束演算法；否則重復步驟2、3。

3. java 最短路徑演算法 如何實現有向 任意兩點

Dijkstra(迪傑斯特拉)演算法是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式

用OPEN,CLOSE表的方式，其採用的是貪心法的演算法策略，大概過程如下：

1、聲明兩個集合，open和close，open用於存儲未遍歷的節點，close用來存儲已遍歷的節點

2、初始階段，將初始節點放入close，其他所有節點放入open

3、以初始節點為中心向外一層層遍歷，獲取離指定節點最近的子節點放入close並從新計算路徑，直至close包含所有子節點

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

5. dijkstra演算法有哪些

迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。

對於圖G=（V，E），將圖中的頂點分成兩組：

第一組S：已求出的最短路徑的終點集合（開始為{v0}）。

第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。

演算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中，直到所有頂點都被加入到第一組頂點集S為止。

(5)迪傑斯特拉演算法java擴展閱讀：

從dis數組選擇最小值，則該值就是源點s到該值對應的頂點的最短路徑，並且把該點加入到T中，此時完成一個頂點，需要看看新加入的頂點是否可以到達其他頂點並且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那麼就替換這些頂點在dis中的值。 然後，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。

6. 矩陣怎麼用來計算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函數結束

7. 尋求大神幫忙寫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};
}
}

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

9. 解釋一下dijkstra演算法這個計算過程的意思 怎麼算的

最近也看到這個演算法，不過主要是通過C語言介紹的，不太一樣，但基本思想差不多。下面只是我個人的看法不一定準確。
Dijkstra演算法主要解決指定某點(源點)到其他頂點的最短路徑問題。
基本思想：每次找到離源點最近的頂點，然後以該頂點為中心(過渡頂點)，最終找到源點到其餘頂點的最短路。

t=1：令源點(v_0)的標號為永久標號(0,λ)(右上角加點), 其他為臨時(+無窮,λ). 就是說v_0到v_0的距離是0，其他頂點到v_0的距離為+無窮。t=1時，例5.3上面的步驟(2)(3)並不能體現

t=2：第1步v_0(k=0)獲得永久標號，記L_j為頂點標號當前的最短距離(比如v_0標號(0,λ)中L_0=0), 邊(v_k,v_j)的權w_kj. 步驟(2)最關鍵，若v_0與v_j之間存在邊，則比較L_k+w_kj與L_j, 而L_k+w_kj=L_0+w_0j<L_j=+無窮。
這里只有v_1,v_2與v_0存在邊，所以當j=1,2時修改標號, 標號分別為(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不變。步驟(3)比較所有臨時標號中L_j最小的頂點, 這里L_1=1最小，v_1獲得永久標號(右上角加點)。

t=3: 第2步中v_1獲得永久標號(k=1), 同第2步一樣，通過例5.3上面的步驟(2)(3)，得到永久標號。 步驟(2),若v_1與v_j(j=2,3,4,5(除去獲得永久標號的頂點))之間存在邊，則比較L_1+w_1j與L_j。這里v_1與v_2，v_3，v_,4存在邊，
對於v_2, L_1+w_12=1+2=3<L_2=4, 把v_2標號修改為(L_1+w_12, v_1)=(3, v_1);
對於v_3, L_1+w_13=1+7=8<L_3=+無窮, 把v_3標號修改為(L_1+w_13, v_1)=(8, v_1);
對於v_4, L_1+w_14=1+5=6<L_4=+無窮, 把v_4標號修改為(L_1+w_14, v_1)=(6, v_1);
v_5與v_1不存在邊，標號不變。步驟(3), 找這些標號L_j最小的頂點，這里v_2標號最小

t=4: k=2, 與v_2存在邊的未獲得永久標號的頂點只有v_4, 比較L_2+w_24=3+1=4<L_4=6, 把v_4標號修改為(L_2+w_24, v_2)=(4, v_2); 其他不變。步驟(3), L_4=4最小。

t=5: k=4, 同理先找v_4鄰接頂點，比較，修改標號，找L_j最小
t=6: 同理

啰嗦的這么多，其實步驟(2)是關鍵，就是通過比較更新最短路徑，右上角標點的就是距離源點最近的頂點，之後每一步就添加一個新的」源點」，再找其他頂點與它的最短距離。

迪傑斯特拉演算法(Dijkstra)(網路)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
裡面有個動圖，更形象地說明了該演算法的過程。(其中每次標注的一個紅色頂點out就和你的這本書中獲得永久標號是相似的)

10. 迪傑斯特拉演算法能用html或者jsp連接資料庫展現出來嗎

首先答案是可以，不過這裡面涉及到很多的程序知識。jsp直接連資料庫是沒有問題，但html是不可以直接連接資料庫的，必須通過程序後端進行連接。涉及知識點有資料庫，jdbc，java，jsp，js等等。