包含dijkstra可視化java的詞條

• 1、求大佬用java幫我實現dijkstra算法，單源最短路徑
• 2、矩陣怎麼用來計算dijkstra算法 java
• 3、速求java 設計一個程序，用Dijkstra算法實現最短路問題，要用圖形用戶界面體現出來，動態靜態都行
• 4、跪求解釋java中shortestpath.DijkstraDistance的具體用法？？？？
• 5、一個有關於java的算法問題，求高手協做

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 = 0

  q = [(0,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”)

怎樣用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函數結束

巧了，前兩天做課程設計，剛做完，不知道你現在還要嗎，要的話加QQ；272614124

聲明：界面上的路徑是畫出來的，結果是同TextField輸出的

//這個算法用來解決無向圖中任意兩點的最短路徑  

public class ShortestDistanceOfTwoPoint_V5 {  

    public static int dijkstra(int[][] W1, int start, int end) {  

        boolean[] isLabel = new boolean[W1[0].length];// 是否標號  

        int[] indexs = new int[W1[0].length];// 所有標號的點的下標集合，以標號的先後順序進行存儲，實際上是一個以數組表示的棧  

        int i_count = -1;//棧的頂點  

        int[] distance = W1.clone();// v0到各點的最短距離的初始值  

        int index = start;// 從初始點開始  

        int presentShortest = 0;//當前臨時最短距離  

        indexs[++i_count] = index;// 把已經標號的下標存入下標集中  

        isLabel[index] = true;  

        while (i_countW1[0].length) {  

            // 第一步：標號v0,即w[0][0]找到距離v0最近的點  

            int min = Integer.MAX_VALUE;  

            for (int i = 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 (int i = 0; i  distance.length; i++) {  

                // 如果vi到那個點有邊，則v0到後面點的距離加  

                if (distance[i] == -1  W1[index][i] != -1) {// 如果以前不可達，則現在可達了  

                    distance[i] = presentShortest + W1[index][i];  

                } else if (W1[index][i] != -1 

                         presentShortest + W1[index][i]  distance[i]) {  

                    // 如果以前可達，但現在的路徑比以前更短，則更換成更短的路徑  

                    distance[i] = presentShortest + W1[index][i];  

                }  

            }  

        }  

        //如果全部點都遍歷完，則distance中存儲的是開始點到各個點的最短路徑  

        return distance – distance;  

    }  

    public static void main(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));  

    }  

}

//參考別人的,自己就懶得寫了,你拿去參考參考…

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.List;

import java.util.Map;

import java.util.Set;

public class Dijkstra {

private int[][] graph;// 加權有向圖

private int start;// 源點編號 從 0開始

private int dimention;

static int INF = Integer.MAX_VALUE / 100;

// 用於標記頂點是否已經計算

private SetInteger vertexSet = new HashSetInteger();

// 存儲結果，Map的key對應各終點編號，value對應路徑編號列表。

private MapInteger, ListInteger pathListMap = new HashMapInteger, ListInteger();

public Dijkstra(int[][] graph, int start) {

this.graph = graph;

this.start = start;

this.dimention = graph.length;

calculate();

}

private void calculate() {

// 初始化

for (int end = 0; end dimention; end++) {

if (end == start) {

continue;

}// 起始點自己的路徑排除。

ListInteger pathList = new ArrayListInteger();

pathList.add(start);// 每條路徑的起始點都為start，pathList只記錄編號，不記錄路徑權值

pathList.add(end);// 每條路徑的第二個參數為終點編號

pathListMap.put(end, pathList);

}

// 計算主體

for (int bridge = 0; bridge dimention; bridge++) {

if (bridge == start) {

continue;

}

if (!vertexSet.contains(bridge)) {// 確保每個基點只循環計算一次

for (int next = 0; next dimention; next++) {

if (next == start || next == bridge) {

continue;

}

if (startTo(bridge) + getRawLength(bridge, next) startTo(next)) {

ListInteger pathList = pathListMap.get(next);

ListInteger bridgePathList = pathListMap.get(bridge);

// 清空，使用新的

pathList.clear();

pathList.addAll(bridgePathList);

pathList.add(next);

}

}

}

vertexSet.add(bridge);

}

// 檢查，是否橋接的路徑都被更新

for (int end = 0; end dimention; end++) {

if (end == start) {

continue;

}

ListInteger pathList = pathListMap.get(end);

int size = pathList.size();

if (size 2) {

for (int end2 = 0; end2 dimention; end2++) {

int isEnd = pathList.get(size – 2);

if (end2 == isEnd) {

pathList.clear();

pathList.addAll(pathListMap.get(end2));

pathList.add(end);

}

}

}

}

}

private int startTo(int end) {

int pathLen = 0;

ListInteger pathList = pathListMap.get(end);

for (int i = 0; i pathList.size() – 1; i++) {

pathLen += graph[pathList.get(i)][pathList.get(i + 1)];

}

return pathLen;

}

private int getRawLength(int start, int end) {

if (end == start) {

return 0;

}

return graph;

}

public int getLength(int end) {

if (end == start) {

return 0;

}

return startTo(end);

}

public void printResult() {

System.out.println(pathListMap);

}

public MapInteger, ListInteger getPathListMap() {

return pathListMap;

}

public static void main(String[] args) {

/*

* int [][] graph = { { INF, 10, INF, 30, 100}, { INF, INF, 50, INF,

* INF}, { INF, INF, INF, INF, 10}, { INF, INF, 20, INF, 60}, { INF,

* INF, INF, INF, INF}};

*/

int[][] graph = { { INF, INF, 10, INF, 30, 100 },

{ INF, INF, 5, INF, INF, INF },

{ INF, INF, INF, 50, INF, INF },

{ INF, INF, INF, INF, INF, 10 },

{ INF, INF, INF, 20, INF, 60 },

{ INF, INF, INF, INF, INF, INF }, };

int start = 0;

int end = 0;

int length = graph.length;

for (start = 0; start length; start++) {

System.out.println();

Dijkstra dijkstra = new Dijkstra(graph, start);

dijkstra.printResult();

for (end = 0; end length; end++) {

if (end == start) {

continue;

}

int len = dijkstra.getLength(end);

System.out.println(” Length(” + start + “-” + end + “) = “

+ ((len == INF) ? “Infinity” : len));

}

}

}

}