Dijkstra算法
Dijkstra算法完成的是找到某個(gè)節(jié)點(diǎn)到其他各個(gè)節(jié)點(diǎn)的最短距離返回一個(gè)距離表，規(guī)定所有路線權(quán)重都是大于0的，一開(kāi)始需要給一個(gè)點(diǎn)椿息，因?yàn)橥瓿傻木褪钦疫@個(gè)點(diǎn)到其他各個(gè)節(jié)點(diǎn)的最短距離。
算法思路：
1）從已經(jīng)解鎖的點(diǎn)中找一個(gè)開(kāi)始點(diǎn)到它最近距離的點(diǎn)
2）解鎖這個(gè)點(diǎn)的所有邊坷衍，更新距離表寝优，距離表中一開(kāi)始沒(méi)有到達(dá)這個(gè)節(jié)點(diǎn)的就新增，之前有的就進(jìn)行更新枫耳。
3）每個(gè)點(diǎn)只處理一次乏矾，進(jìn)行了一次解鎖邊集和更新距離表后就將它鎖住，返回1繼續(xù)操作直到所有可達(dá)節(jié)點(diǎn)都處理一遍即可拿到最小距離表。
為什么Dijkstra算法能夠拿到最短距離呢钻心？
我簡(jiǎn)單說(shuō)說(shuō)凄硼，嚴(yán)格證明就不談，我也不會(huì)捷沸。首先摊沉，從已經(jīng)解鎖的點(diǎn)中找到可以到達(dá)的最小距離。比如下面的這個(gè)圖痒给，從v1開(kāi)始進(jìn)行算法说墨。
1.解鎖的有v1,拿出v1,v1所能到達(dá)的點(diǎn)，{v6,v5,v3}解鎖更新距離表為{v1:0,v6:100,v5:30,v3:10}
2.從已經(jīng)解鎖的點(diǎn)集中找到可達(dá)的最短距離的點(diǎn)苍柏，那就是v3尼斧，為什么要拿最小的呢？為什么一個(gè)點(diǎn)處理完之后就可以不管了呢试吁？
原因是如果你是從已經(jīng)解鎖的點(diǎn)中找到的最短距離的點(diǎn)棺棵，那就說(shuō)明這就是開(kāi)始點(diǎn)能到達(dá)它的最短距離，就像是上面第二次處理v3潘悼，v3是v1的所有直達(dá)點(diǎn)中最短的律秃，那么就說(shuō)明從其他直達(dá)點(diǎn)走再繞回v3，在邊權(quán)值大于0的前提下距離不可能比v1直達(dá)v3要短治唤。
每次都選出一個(gè)可達(dá)的最短距離棒动，最終將所有點(diǎn)都找出來(lái)，那么每個(gè)點(diǎn)肯定是可達(dá)最短距離的加和宾添，這就是貪心策略船惨。
java實(shí)現(xiàn)Dijkstra算法1.0
public static HashMap<Node, Integer> dijkstra(Node begin) {
if (begin == null) return null;
HashMap<Node, Integer> nodeDistanceMap = new HashMap<>();
nodeDistanceMap.put(begin, 0);
//鎖住已經(jīng)處理過(guò)的節(jié)點(diǎn)
HashSet<Node> selectedNode = new HashSet<>();
//每次找到當(dāng)前距離最短的節(jié)點(diǎn)
while (true) {
int minDistance = Integer.MAX_VALUE;
Node minNode = null;
for (Map.Entry<Node, Integer> entry : nodeDistanceMap.entrySet()) {
Integer distance = entry.getValue();
if (!selectedNode.contains(entry.getKey()) && distance < minDistance) {
minDistance = distance;
minNode = entry.getKey();
}
}
if (minDistance == Integer.MAX_VALUE) break;
for (Edge next : minNode.edges) {
if (!nodeDistanceMap.containsKey(next.to)) {
nodeDistanceMap.put(next.to, minDistance + next.weight);
} else {
nodeDistanceMap.put(next.to, Math.min(nodeDistanceMap.get(next.to), minDistance + next.weight));
}
}
//鎖住Node,以后不用管它了
selectedNode.add(minNode);
}
return nodeDistanceMap;
改良一下代碼，不是優(yōu)化缕陕，就是將找最小到達(dá)點(diǎn)功能給抽離出來(lái)粱锐。
//將找到最小距離的節(jié)點(diǎn)給抽離出一個(gè)函數(shù)，其實(shí)是再寫一遍扛邑，不太熟練
public static HashMap<Node, Integer> dijkstra1(Node begin) {
if (begin == null) return null;
HashMap<Node, Integer> distanceMap = new HashMap<>();
distanceMap.put(begin, 0);
HashSet<Node> lockedNodes = new HashSet<>();
Node minNode;
while ((minNode = getMinDistanceNode(distanceMap, lockedNodes)) != null) {
for (Edge edge : minNode.edges) {
Integer distance = distanceMap.get(minNode);
Node to = edge.to;
if (!distanceMap.containsKey(to)) {
//add
distanceMap.put(to, distance + edge.weight);
} else {
//update
distanceMap.put(to, Math.min(distance + edge.weight, distanceMap.get(to)));
}
}
lockedNodes.add(minNode);//鎖住
}
return distanceMap;
}
public static Node getMinDistanceNode(HashMap<Node, Integer> distanceMap, HashSet<Node> lockedNodes) {
int min = Integer.MAX_VALUE;
Node minNode = null;
for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
if (!lockedNodes.contains(entry.getKey()) && entry.getValue() < min) {
min = entry.getValue();
minNode = entry.getKey();
}
}
return minNode;
}
優(yōu)化2.0版本怜浅，這才是進(jìn)行了優(yōu)化
思考：
通過(guò)研究dijkstra算法我們可以發(fā)現(xiàn)，核心就兩點(diǎn)
1）每次都找到那個(gè)最小距離的到達(dá)點(diǎn)蔬崩，
2）遍歷那個(gè)最小距離的點(diǎn)更新距離表
很明顯第二點(diǎn)是不可能優(yōu)化的恶座，你總得看看所有的邊看看距離怎么樣然后更新距離表。
但是第一點(diǎn)找到最小距離沥阳，我們很容易會(huì)想到使用最小堆是否能夠優(yōu)化跨琳，答案是可以的。
因?yàn)樽钚《衙看芜M(jìn)行堆的調(diào)整也不過(guò)是logN,也就是說(shuō)我們可以直接使用一個(gè)小根堆來(lái)存儲(chǔ)距離表
不過(guò)注意一點(diǎn)桐罕，因?yàn)榫嚯x表中的距離是需要進(jìn)行更新的脉让，所以我們需要更新后保證堆正確性桂敛，這就不能使用PriorityQueue,需要我們自己實(shí)現(xiàn)resign功能，這需要維護(hù)一個(gè)indexMap需要知道哪個(gè)位置的元素發(fā)生了更新溅潜，這個(gè)更新只會(huì)變小术唬，不會(huì)變大，所以肯定是向上進(jìn)行heapInsert
如何在堆中完成一個(gè)節(jié)點(diǎn)的鎖住功能伟恶，避免已經(jīng)處理過(guò)的節(jié)點(diǎn)再次插入堆中?
做以下約定
1）如果indexMap中沒(méi)有這個(gè)Node碴开，那肯定還沒(méi)有，就直接加入
2）如果有博秫，但是index為-1潦牛，則表示加入過(guò)，但是已經(jīng)彈出挡育，直接跳過(guò)巴碗，彈出的肯定是找到最小距離了
- 以上都不符合表示還在堆中，進(jìn)行更新操作即寒，需要維護(hù)堆
實(shí)現(xiàn)
用來(lái)找最小到達(dá)點(diǎn)的堆
public static class Heap {
private static class NodeRecord {
private Node node;
private Integer distance;
public NodeRecord(Node node, Integer distance) {
this.node = node;
this.distance = distance;
}
}
private ArrayList<NodeRecord> eleMentData;//Entry<Node,distance>
private HashMap<Node, Integer> indexMap;//這里的Integer是下標(biāo)
private int heapSize;
public Heap() {
eleMentData = new ArrayList<>();
indexMap = new HashMap<>();
}
public void swap(int aIdx, int bIdx) {
//保證下標(biāo)隨著一起改
NodeRecord aEntry = eleMentData.get(aIdx);
NodeRecord bEntry = eleMentData.get(bIdx);
eleMentData.set(aIdx, bEntry);
eleMentData.set(bIdx, aEntry);
indexMap.put(aEntry.node, bIdx);
indexMap.put(bEntry.node, aIdx);
}
public void heapInsert(int index) {
int father;
//維護(hù)一個(gè)小根堆橡淆，如果父節(jié)點(diǎn)的distance比這個(gè)子節(jié)點(diǎn)要大的話需要交換
while (compare(index, (father = (index - 1) / 2)) < 0) {
swap(father, index);
}
}
public void heapify(int index) {
int leftChild;
while ((leftChild = (index << 1) | 1) < heapSize) {
int lowest = leftChild + 1 < heapSize && compare(leftChild + 1, leftChild) < 0 ? leftChild + 1 : leftChild;
lowest = compare(index, lowest) < 0 ? index : lowest;
if (index == lowest) break;
swap(index, lowest);
index = lowest;
}
}
//比較兩個(gè)下標(biāo)處的Entry里distance大小
private int compare(int i1, int i2) {
return eleMentData.get(i1).distance - eleMentData.get(i2).distance;
}
//進(jìn)行三個(gè)情況的檢查和處理，完成操作
public void addOrUpdateOrIgnore(Node node, int distance) {
if (!indexMap.containsKey(node)) {//add
eleMentData.add(heapSize, new NodeRecord(node, distance));
//indexMap同步
indexMap.put(node,heapSize++);
heapInsert(heapSize - 1);
} else if (indexMap.get(node) != -1) {//update
Integer index = indexMap.get(node);
eleMentData.get(index).distance = Math.min(eleMentData.get(index).distance, distance);
heapInsert(index);//可能更新母赵，維護(hù)一下
}
}
public NodeRecord poll() {
if (isEmpty()) throw new RuntimeException("no more ele...");
final NodeRecord res = eleMentData.get(0);
swap(0,--heapSize);
eleMentData.set(heapSize,null);
indexMap.put(res.node,-1);//-1:曾經(jīng)來(lái)過(guò)
heapify(0);
return res;
}
public boolean isEmpty() {
return heapSize == 0;
}
}
算法本身
public static HashMap<Node,Integer> dijkstra(Node begin){
if(begin==null) return null;
HashMap<Node,Integer> result = new HashMap<>();
Heap smallRHeap = new Heap();
smallRHeap.addOrUpdateOrIgnore(begin,0);
while (!smallRHeap.isEmpty()){
Heap.NodeRecord heapTop = smallRHeap.poll();
for(Edge edge:heapTop.node.edges){
smallRHeap.addOrUpdateOrIgnore(edge.to,edge.weight+heapTop.distance);
}
result.put(heapTop.node,heapTop.distance);
}
return result;
}
測(cè)試
用上面那個(gè)例子進(jìn)行測(cè)試
public static void main(String[] args) {
int[][] matrix = {{10, 1, 3}, {100, 1, 6}, {30, 1, 5}, {5, 2, 3}, {50, 3, 4}, {20, 5, 4}, {10, 4, 6}, {60, 5, 6},};
Graph graph = GraphGenerator.graphGenerator(matrix);
HashMap<Node, Integer> result = dijkstra(graph.nodesMap.get(1));
for (Map.Entry<Node, Integer> entry : result.entrySet()) {
System.out.println("to Node{" + entry.getKey().value + "} distance:" + entry.getValue());
}
}
這里的Graph是我自己熟悉的圖的表示方式逸爵，matrix是一個(gè)邊組成的二維數(shù)組，里面存的每個(gè)一維數(shù)組都是這樣的意思{weight,from,to}
Graph
public class Graph{
private HashMap<Integer,Node> nodes;//Node.value map to Node
private HashSet<Edge> edges;
public Graph(){
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
Node
public class Node{
private int in;
private int out;
private int value;
private ArrayList<Node> nexts;
private ArrayList<Edge> edges;
public Node(){
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
Edge
public class Edge{
private int weight;
private int from;//from Node's value
private int to;//to Node's value
public Edge(int weight,int from,int to){
this.weight = weight;
this.from = from;
this.to = to;
}
}
