首先dijkstra是一个人，一位计算机上古时期的先驱；而dijkstra是他用来向观众解释什么计算机想到的一个算法，如何计算两个地点的最短距离；当然这个最短距离，是有一个前提的，首先你要有一个已知各个点之间距离的路网；
比如这个图，我们如何去寻找A点到E点的最短距离？显然，正常人的直觉就是“这不是很简单，我都算下试试，比较一下不就知道了！”。但是这里只有四个顶点，倘若，除了这四个顶点外，额外还有有100个顶点的路网，又如何找到两个点的最短距离呢？这个时候，也许就要好好想想 “首先我要一个笔记本，一个笔，看下哪些点能到我的目的地E点，我可以给这些点起个名字，就叫‘nearByEPoints’，然后，我只需要知道，这些‘nearByEPoints’点到起点A的最短路径，然后加上末端的一段路径距离，比较一下就能知道那个路径是最短路径了；然后问题就变成了，如何找到A点到nearByEPoints”点的最短路径了，可以想见，只要我们不怕麻烦肯定能找到A到E的最短路径的；”
从刚刚的思路中，我们可以知道，我们可以使用递归算法来实现这个算法。
dijkstra算法可视化
/**
* @program: SpringBoot_Dubbo_Example
* @description: 计算主体
* @author: wangJun
* @create: 2019-10-22 16:07
**/
public class DPQ {
private LinkedList<Line> linesNeedToCalculate;
public DPQ(LinkedList<Line> linesNeedToCalculate) {
this.linesNeedToCalculate = linesNeedToCalculate;
}
/**
* 这里递归计算的缺点之一是，可能存在重复计算，这里使用了shortestMap来缓存以及计算过的节点
* @param startPoint
* @param destPoint
* @param lines
* @param shortestMap
* @return
*/
long getShortestDistance(long startPoint, long destPoint, LinkedList<Line> lines, HashMap<Long, Long> shortestMap){
if (destPoint == startPoint){
return 0;
}
if (shortestMap.get(destPoint) != null){
return shortestMap.get(destPoint);
}
Iterator<Line> iterator = lines.iterator();
long shortestDistance = -1;
while (iterator.hasNext()){
Line currentLine = iterator.next();
if (currentLine.getToPoint() == destPoint){
iterator.remove();
LinkedList<Line> remainLines = new LinkedList<>();
remainLines.addAll(lines);
long beforeShortestDistance = getShortestDistance(startPoint, currentLine.getFromPoint(), remainLines, shortestMap);
Long currentDistance = beforeShortestDistance + currentLine.getDistance();
if (currentDistance < shortestDistance || shortestDistance == -1){
shortestDistance = currentDistance;
}
}
}
System.out.println(startPoint + "到" + destPoint + " 最短距离是" + shortestDistance);
shortestMap.put(destPoint, shortestDistance);
return shortestDistance;
}
}
我们可以知道任何递归都可以改造成循环方式，我用C++又实现了一版普通循环方式的dijkstra
Dijkstra.h
#ifndef DATASTRUCTURE_DIJKSTRA_H
#define DATASTRUCTURE_DIJKSTRA_H
#include <vector>
#include <list>
#include <utility>
using namespace std;
class Dijkstra {
public:
/**
* 顶点个数
*/
int v;
/**
* 一个二维数组，index1，index2是两个顶点，value是之间直接的距离，如果不相连接，就是INX_MAX
*/
vector<int> *adj;
Dijkstra(int vertexCount);
/**
* search入口
* @param s
* @param t
* @return
*/
list<int> search(int s, int t);
/**
* 获取下一次计算的起始点（最短的未settle的点）
* @param settled
* @param shortest
* @return
*/
int getNextStart(bool settled[], int shortest[]);
};
#endif //DATASTRUCTURE_DIJKSTRA_H
Dijkstra.cpp
#include "Dijkstra.h"
#include <vector>
#include <list>
#include <cmath>
Dijkstra::Dijkstra(int vertexCount) {
this->v = vertexCount;
this->adj = new vector<int>[v];
}
list<int> Dijkstra::search(int s, int t) {
list<int> result;
if (s == t){
result.push_front(s);
return result;
}
bool settled[v];
int pre[v];
int shortest[v];
//初始化字段
for (int i = 0; i < v; ++i) {
settled[i] = false;
pre[i] = -1;
shortest[i] = INT_MAX;
}
settled[s] = false;
shortest[s] = 0;
while(true){
int thisStart = getNextStart(settled, shortest);
if(thisStart == -1){
//可连通的线路已经全部遍历完毕
break;
} else {
settled[thisStart] = true;
}
vector<int> sides = adj[thisStart];
for (int point = 0; point < v; ++point) {
if (settled[point]){
continue;
}
int length = sides.at(point);
//s 和 point 相互连接，且不是自己连自己
if (length != INT_MAX && thisStart != point){
int newLength = shortest[thisStart] + length;
if(shortest[point] > newLength){
shortest[point] = newLength;
pre[point] = thisStart;
}
}
}
}
//如果s到t是可达的
if (settled[t]){
result.push_front(t);
while(true){
if(pre[t] != -1){
result.push_front(pre[t]);
t = pre[t];
} else {
break;
}
}
}
return result;
}
int Dijkstra::getNextStart(bool *settled, int *shortest) {
int unsettledAndShortestIndex = -1;
int unsettledAndShortestDistance = INT_MAX;
for (int i = 0; i < v; ++i) {
bool isSettle = settled[i];
int distance = shortest[i];
if (!isSettle && distance < unsettledAndShortestDistance){
unsettledAndShortestIndex = i;
unsettledAndShortestDistance = distance;
}
}
return unsettledAndShortestIndex;
}
测试代码：DijkstraTest.cpp
#include "gtest/gtest.h"
#include "graph/Dijkstra.h"
#include <iostream>
#include <cmath>
#include <list>
using namespace std;
class DijkstraTestFixture: public ::testing::Test {
public:
Dijkstra *dijkstra;
virtual void SetUp(){
int vertexCount = 5;
dijkstra = new Dijkstra(vertexCount);
dijkstra->adj = new vector<int>[vertexCount];
dijkstra->adj[0] = {0,7, 5, INT_MAX, INT_MAX};
dijkstra->adj[1] = {7,0, 4, 6, INT_MAX};
dijkstra->adj[2] = {5,4, 0, INT_MAX, 1};
dijkstra->adj[3] = {INT_MAX,6, INT_MAX, 0, INT_MAX};
dijkstra->adj[4] = {INT_MAX,INT_MAX, 1, INT_MAX, 0};
}
virtual void TearDown(){
delete dijkstra;
}
};
TEST_F(DijkstraTestFixture, testBasic) {
list<int> result = dijkstra->search(0, 4);
list<int>::iterator it;
for(it = result.begin(); it != result.end(); it++){
cout << *it << endl;
}
}