快捷導(dǎo)航

Java 迪杰斯特拉算法實現(xiàn)查找最短距離的實現(xiàn)

更新時間：2019年09月03日 14:40:39 作者：gmHappy

這篇文章主要介紹了Java 迪杰斯特拉算法實現(xiàn)查找最短距離的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

迪杰斯特拉算法

迪杰斯特拉算法是由荷蘭計算機科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。具體的計算規(guī)則我們可以通過下圖進行查看。

在這里插入圖片描述

通過這幅圖我們可以簡單的理解迪杰斯特拉算法算法的基礎(chǔ)思路，下面我們就通過JAVA來實現(xiàn)這個算法。

算法實現(xiàn)

在迪杰斯特拉算法中我們需要保存從起點開始到每一個節(jié)點最短步長，這也是圖中需要比較得出的步長，同時我們還需要存儲該步長下的前一個節(jié)點是哪個，這樣我們就可以通過終點一個一個往前推到起點，這樣就出來了完整的最優(yōu)路徑。

每一個節(jié)點的最優(yōu)前一節(jié)點

public class PreNode {
	private String preNodeName;//最優(yōu)的前一個節(jié)點
	private int nodeStep;// 起點到前一個節(jié)點的步長+前一個節(jié)點本身的步長

	public PreNode(String preNodeName, int nodeStep) {
		this.preNodeName = preNodeName;
		this.nodeStep = nodeStep;
	}

	public String getPreNodeName() {
		return preNodeName;
	}

	public void setPreNodeName(String preNodeName) {
		this.preNodeName = preNodeName;
	}

	public int getNodeStep() {
		return nodeStep;
	}

	public void setNodeStep(int nodeStep) {
		this.nodeStep = nodeStep;
	}
}

定義返回的數(shù)據(jù)結(jié)構(gòu)

package dijkstra;

import java.util.List;

public class MinStep {
	private boolean reachable;// 是否可達
	private int minStep;// 最短步長
	private List<String> step;// 最短路徑

	public MinStep() {
	}

	public MinStep(boolean reachable, int minStep) {
		this.reachable = reachable;
		this.minStep = minStep;
	}

	public boolean isReachable() {
		return reachable;
	}

	public void setReachable(boolean reachable) {
		this.reachable = reachable;
	}

	public int getMinStep() {
		return minStep;
	}

	public void setMinStep(int minStep) {
		this.minStep = minStep;
	}

	public List<String> getStep() {
		return step;
	}

	public void setStep(List<String> step) {
		this.step = step;
	}
}

定義接口

package dijkstra;
 
import java.util.HashMap;

public interface Distance {
	public static final MinStep UNREACHABLE = new MinStep(false, -1);
	/**
	 * @param start
	 * @param end
	 * @param stepLength
	 * @return
	 * @Description: 起點到終點的最短路徑
	 */
	public MinStep getMinStep(String start, String end, final HashMap<String, HashMap<String, Integer>> stepLength);
}

功能實現(xiàn)

package dijkstra;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

public class DistanceDijkstraImpl implements Distance {
	// 圖中相鄰兩個節(jié)點的距離
	private HashMap<String, HashMap<String, Integer>> stepLength;
	// 非獨立節(jié)點個數(shù)
	private int nodeNum;
	// 移除節(jié)點
	private HashSet<String> outNode;
	// 起點到各點的步長，key為目的節(jié)點，value為到目的節(jié)點的步長
	private HashMap<String, PreNode> nodeStep;
	// 下一次計算的節(jié)點
	private LinkedList<String> nextNode;
	// 起點、終點
	private String startNode;
	private String endNode;

	/**
	 * @param start
	 * @param end
	 * @param stepLength
	 * @return
	 * @Description: start 到 end 的最短距離
	 */
	public MinStep getMinStep(String start, String end, final HashMap<String, HashMap<String, Integer>> stepLength) {
		this.stepLength = stepLength;
		this.nodeNum = this.stepLength != null ? this.stepLength.size() : 0;
		// 起點、終點不在目標(biāo)節(jié)點內(nèi)，返回不可達
		if (this.stepLength == null || (!this.stepLength.containsKey(start)) || (!this.stepLength.containsKey(end))) {
			return UNREACHABLE;
		}
		initProperty(start, end);
		step();
		if (nodeStep.containsKey(end)) {
			return changeToMinStep();
		}
		return UNREACHABLE;
	}

	/**
	 * 返回最短距離以及路徑
	 */
	private MinStep changeToMinStep() {
		MinStep minStep = new MinStep();
		minStep.setMinStep(nodeStep.get(endNode).getNodeStep());
		minStep.setReachable(true);
		LinkedList<String> step = new LinkedList<String>();
		minStep.setStep(step);
		// 先將終點添加到路徑第一位中
		String tempNode = endNode;
		step.addFirst(tempNode);
		// 再將所經(jīng)過的節(jié)點添加到路徑第一位中
		while (nodeStep.containsKey(tempNode)) {
			PreNode preNode = nodeStep.get(tempNode);
			String preNodeName = preNode.getPreNodeName();
			// System.out.println(preNodeName + " " + preNode.getNodeStep());
			step.addFirst(preNodeName);
			tempNode = preNodeName;
		}
		return minStep;
	}

	/**
	 * @param start
	 * @Description: 初始化屬性
	 */
	private void initProperty(String start, String end) {
		outNode = new HashSet<String>();
		nodeStep = new HashMap<String, PreNode>();
		nextNode = new LinkedList<String>();
		nextNode.add(start);
		startNode = start;
		endNode = end;
	}

	/**
	 * @param end
	 * @Description:
	 */
	private void step() {
		if (nextNode == null || nextNode.size() < 1) {
			return;
		}
		if (outNode.size() == nodeNum) {
			return;
		}
		// 獲取下一個計算節(jié)點
		String start = nextNode.removeFirst();
		// 到達該節(jié)點的最小距離
		int step = 0;
		if (nodeStep.containsKey(start)) {
			step = nodeStep.get(start).getNodeStep();
		}
		// 獲取該節(jié)點可達節(jié)點
		HashMap<String, Integer> nextStep = stepLength.get(start);
		Iterator<Entry<String, Integer>> iter = nextStep.entrySet().iterator();
		while (iter.hasNext()) {
			Entry<String, Integer> entry = iter.next();
			String key = entry.getKey();
			// 如果是起點到起點，不計算之間的步長
			if (key.equals(startNode)) {
				continue;
			}
			// 起點到可達節(jié)點的距離
			Integer value = entry.getValue() + step;
			if ((!nextNode.contains(key)) && (!outNode.contains(key))) {
				nextNode.add(key);
			}
			if (nodeStep.containsKey(key)) {
				// 比較步長
				if (value < nodeStep.get(key).getNodeStep()) {
					nodeStep.put(key, new PreNode(start, value));
				}
			} else {
				nodeStep.put(key, new PreNode(start, value));
			}
		}
		// 將該節(jié)點移除
		outNode.add(start);
		// 計算下一個節(jié)點
		step();
	}
}

step()邏輯解析

這一步也就是迪杰斯特拉算法的核心部分，在計算的過程中，我們需要進行如下步驟：

1）判斷是否達到終止條件，如果達到終止條件，結(jié)束本次算法，如果沒有達到，執(zhí)行下一步；（終止條件：下一次需要計算的節(jié)點隊列沒有數(shù)據(jù)或已經(jīng)計算過的節(jié)點數(shù)等于節(jié)點總數(shù)）

2）獲取下一次計算的節(jié)點A；

3）從起點到各節(jié)點之間的最短距離map中獲取到達A點的最小距離L；

4）獲取A節(jié)點的可達節(jié)點B，計算從起點先到A再到B是否優(yōu)于已有的其他方式到B，如果優(yōu)于，則更新B節(jié)點，否則不更新；

5）判斷B是否是已經(jīng)移除的節(jié)點，如果不是移除的節(jié)點，把B添加到下一次需要計算的節(jié)點隊列中，否則不做操作；

6）判斷A節(jié)點是否還有除B以外的其他節(jié)點，如果有，執(zhí)行第4）步，否則執(zhí)行下一步；

7）將A節(jié)點從下一次需要計算的節(jié)點中移除添加到已經(jīng)計算過的節(jié)點中；

8）執(zhí)行第一步。

Demo運行

import java.util.HashMap;
import com.alibaba.fastjson.JSONObject;

public class DistanceTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HashMap<String, HashMap<String, Integer>> stepLength = new HashMap<String, HashMap<String, Integer>>();
		HashMap<String, Integer> step1 = new HashMap<String, Integer>();
		stepLength.put("1", step1);
		step1.put("2", 2);

		HashMap<String, Integer> step2 = new HashMap<String, Integer>();
		stepLength.put("2", step2);
		step2.put("1", 2);
		step2.put("3", 1);

		HashMap<String, Integer> step3 = new HashMap<String, Integer>();
		stepLength.put("3", step3);
		step3.put("2", 1);
		step3.put("4", 1);
		step3.put("9", 1);

		HashMap<String, Integer> step4 = new HashMap<String, Integer>();
		stepLength.put("4", step4);
		step4.put("5", 1);
		step4.put("3", 1);

		HashMap<String, Integer> step5 = new HashMap<String, Integer>();
		stepLength.put("5", step5);
		step5.put("4", 1);

		HashMap<String, Integer> step6 = new HashMap<String, Integer>();
		stepLength.put("6", step6);
		step6.put("9", 1);

		HashMap<String, Integer> step7 = new HashMap<String, Integer>();
		stepLength.put("7", step7);
		step7.put("10", 1);

		HashMap<String, Integer> step8 = new HashMap<String, Integer>();
		stepLength.put("8", step8);
		step8.put("11", 3);

		HashMap<String, Integer> step9 = new HashMap<String, Integer>();
		stepLength.put("9", step9);
		step9.put("3", 1);
		step9.put("6", 1);
		step9.put("10", 1);

		HashMap<String, Integer> step10 = new HashMap<String, Integer>();
		stepLength.put("10", step10);
		step10.put("9", 1);
		step10.put("7", 1);
		step10.put("11", 1);

		HashMap<String, Integer> step11 = new HashMap<String, Integer>();
		stepLength.put("11", step11);
		step11.put("8", 3);
		step11.put("10", 1);

		System.out.println(JSONObject.toJSON(stepLength));

		Distance distance = new DistanceDijkstraImpl();
		MinStep step = distance.getMinStep("1", "5", stepLength);
		System.out.println(JSONObject.toJSON(step));

		step = distance.getMinStep("1", "8", stepLength);
		System.out.println(JSONObject.toJSON(step));

		step = distance.getMinStep("8", "1", stepLength);
		System.out.println(JSONObject.toJSON(step));

		step = distance.getMinStep("11", "7", stepLength);
		System.out.println(JSONObject.toJSON(step));

		step = distance.getMinStep("10", "8", stepLength);
		System.out.println(JSONObject.toJSON(step));
	}

}

{“11”:{“8”:1,“10”:1},“1”:{“2”:2},“2”:{“1”:2,“3”:1},“3”:{“4”:1,“9”:1,“2”:1},“4”:{“5”:1,“3”:1},“5”:{“4”:1},“6”:{“9”:1},“7”:{“10”:1},“8”:{“11”:1},“9”:{“6”:1,“3”:1,“10”:1},“10”:{“11”:1,“9”:1,“7”:1}}
{“minStep”:5,“step”:[“1”,“2”,“3”,“4”,“5”],“reachable”:true}
{“minStep”:7,“step”:[“1”,“2”,“3”,“9”,“10”,“11”,“8”],“reachable”:true}
{“minStep”:7,“step”:[“8”,“11”,“10”,“9”,“3”,“2”,“1”],“reachable”:true}
{“minStep”:2,“step”:[“11”,“10”,“7”],“reachable”:true}
{“minStep”:2,“step”:[“10”,“11”,“8”],“reachable”:true}

在這里插入圖片描述