时代Java，与您同行！关注微信公众号，关注前沿技术，微信搜索：nowjava或时代Java，也可点击这里扫码关注

时代Java

Java Dijakstra算法的实现。

欢马劈雪

工程师 (已认证)

原创分享签约作者

发表于实例源码

556

Dijakstra算法的实现。

实例源码：

源代码：

执行

执行中...

import java.util.ArrayList;

import java.util.Comparator;/*来 自 N o w J a v a . c o m - 时代Java*/

import java.util.HashMap;

import java.util.PriorityQueue;

//This is an implementation of Dijakstra algorithm. It computes the single source minimum distances for a positive weighted graph.

public class Dijakstra {

/**

* Computes the minimum distances between s and all the other nodes for a POSITIVE weighted graph.

* @param s int representing the source node number

* @param gWeights it's a matrix V*V where V is the number of verticies. gWeights[u][v] = w if there is an edge between u and v of weight w, gWeights[u][u]=0, gWeights[u][v]=INTEGER.MAX_INT if there is no edge between u and v

* @param gAdjencyList it's an arraylist of size V (where V is the number of verticies) that contains the neighbors for all the nodes. gAdjencyList[u] is a list that contains the nodes v such that there is an edge u->v

* @return the minimal distance from s to every node. The keys are the nodes and the values are the minimum distances

public static HashMap<Integer, Integer> dijakstra(int s,

int[][] gWeights, ArrayList<ArrayList<Integer>> gAdjencyList) {

HashMap<Integer, Integer> nonVisitedNodes = new HashMap<Integer, Integer>(); //contains the non visited nodes as a key and their current computed distance to s as a value

PriorityQueue<int[]> minValue = new PriorityQueue<int[]>(10,

new Comparator<int[]>() {

public int compare(int[] arg0, int[] arg1) {

if (arg0[1] == arg1[1]) {

return new Integer(arg0[0])

.compareTo(new Integer(arg1[0]));

}

return new Integer(arg0[1]).compareTo(new Integer(

arg1[1]));

}/* 来自 时 代 J a v a 公 众 号*/

});//will store the minimal value of the non visited nodes. Could optimize runtime if we store the two min values in variables.

for (int i = 0; i < gAdjencyList.size(); i++) {

nonVisitedNodes.put(i, Integer.MAX_VALUE);

if (i != s)

minValue.add(new int[] { i, Integer.MAX_VALUE });

} //initialize non visited nodes with infiniy distances

HashMap<Integer, Integer> visitedNodes = new HashMap<Integer, Integer>(); //contains the nodes visited as a key and their distances to s as a value. Initially empty

HashMap<Integer, Integer> parents = new HashMap<Integer, Integer>(); //contains the nodes as a key and the parent node in the optimal path from s as a value.

//start with the node s.

minValue.add(new int[] { s, 0 });

parents.put(s, null);

while (!nonVisitedNodes.isEmpty()) {

//visit the node that has the current minimal distance

int currentNode = minValue.peek()[0];

int value = minValue.poll()[1];

visitedNodes.put(currentNode, value);

nonVisitedNodes.remove(currentNode);

//update the distance of all his non visited neighbors

for (int i = 0; i < gAdjencyList.get(currentNode).size(); i++) {

int neighbor = gAdjencyList.get(currentNode).get(i);

if (nonVisitedNodes.containsKey(neighbor)

&& value + gWeights[currentNode][neighbor] < nonVisitedNodes

.get(neighbor)) {

int neighValue = value

+ gWeights[currentNode][neighbor];

nonVisitedNodes.put(neighbor, neighValue);

minValue.add(new int[] { neighbor, neighValue });

parents.put(neighbor, currentNode);

}

return visitedNodes;

}

public static void main(String[] args) {

int[][] gWeights = new int[][] { { 0, 5, -1, 9, 0, 2 },

{ 5, 0, 2, -1, -1, -1 }, { -1, 2, 0, 3, -1, -1 },

{ 9, -1, 3, 0, 2, -1 }, { -1, -1, -1, 2, 0, 3 },

{ 2, -1, -1, -1, 3, 0 } };

ArrayList<ArrayList<Integer>> gAdjency = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> neighbors0 = new ArrayList<Integer>();

neighbors0.add(1);

neighbors0.add(3);

neighbors0.add(5);

ArrayList<Integer> neighbors1 = new ArrayList<Integer>();

neighbors1.add(0);

neighbors1.add(2);

ArrayList<Integer> neighbors2 = new ArrayList<Integer>();

neighbors2.add(1);

neighbors2.add(3);
/**代码未完, 请加载全部代码(NowJava.com).**/

编辑/阅读全部代码

执行结果：

本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。

编辑于 2020-03-26 09:23:272020-03-26 09:23:27

实例源码

实例源码订阅