Dijkstra算法工作过程
Dijkstra算法是给定一个起点也就是原点，然后该原点通过与它临近的顶点不断向外扩张，最终得到该原点到其它所有顶点得最短距离。
算法核心流程
v或者u代表顶点和其它节点，(u,v)表示两个节点连接的线，weight(u,v)则表示v到u的权重(也可以理解为距离或者到达该顶点的成本)，以上图为例子，A(0)原点到上方顶点表述为(u,v)，weight(u,v)=3。
定义一个数组dist，记录原点(s)到其它所有节点的最短距离，该数组长度为所有顶点数量，下标则代表各个顶点，在初始化的时候dist(s)=0而到其它顶点的距离都为dist(u)=∞(无穷大)，因为除了原点以外，到其它节点的距离都还是未知的。
定义队列q，将所有顶点都添加到队列q中，当到所有顶点的距离都计算完成后，该队列为空。
定义集合s，将所有已经访问过的顶点都添加到该集合s中，当所有顶点的距离都计算完成后，该集合包含所有顶点。
1.如果队列不为空，则从队列q中pop出一个顶点v并且该顶点v不存在于集合s中，因为原点是第一个被初始化的顶点，所以q队列中pop出的第一个顶点一定是原点。
2.将顶点v添加到集合s中，表示该顶点已经被访问过了。
4.取出与顶点v相关联的临近点u，并计算原点顶点v到u的权重(成本)dist(v) + weight(u,v) ，如果得到的权重小于当前临近点u的权重，也就是dist(v) + weight(u,v) < dist(u)，则更新临近顶点u的权重。
第4步是非常核心的步骤，整个计算过程就是靠着第四步，靠着第一个已经初始化的原点不断去初始化或者更新临近点的权重(距离成本)并重复这个过程得到原点到所有顶点的最短距离。
下面是伪码实现:
function Dijkstra(Graph, source):
dist[source] := 0 // 初始化原点(起点)的距离为0
for each vertex v in Graph: //初始化队列q流程
if v ≠ source
dist[v] := infinity // 除了原点以为的顶点都定义为无穷大
add v to Q // 将顶点添加到队列Q
while Q is not empty: // 开始处理队列Q中的所有顶点
v := vertex in Q with min dist[v] // 从队列Q中得到最小距离顶点v，因为只有原点初始化为0所以第一个是原点
remove v from Q
for each neighbor u of v: // 临近点还未从队列Q中移除
alt := dist[v] + length(v, u)
if alt < dist[u]: // 如果找到了最短距离
dist[u] := alt // 更新最短距离
return dist[]
end function
图解
根据前面描述的流程，一开始只初始化起点也就是原点A的距离为0，而A到其它顶点的距离都是无穷大，因为都还未知，而顶点与各个节点之间的权重(成本)都以灰色数字表示。
按照伪码描述的核心流程，与A临近的3个点都被找到，而刚开始的临近的3个节点值都为无穷大，以临近的第一个点为例子，原点距离dist[v]=0，原点v到临近的第一个顶点u的权重为length(v,u)=3，按照之前描述的方式alt = dist[v] + length(v, u)得到3，因为这个时候第一个临近点的权重为无穷大，所以if alt < dist[u]成立，并更新了第一个临近点的权重为3，也就是原点到这个点的成本为3，其它两个点都是以此方式计算。
与开头时候说的一样，该算法依靠以一个原点为基础不断向外扩张，最终得到原点到所有节点的最短距离，下图描述了这个情况，与原点A临近的三个顶点都更新了权重，不再是无穷大，这个时候以权重3的节点为例子，权重3的节点找到与自己临近的两个点，这两个点同样刚开始都是无穷大，以同样的方式计算，并以第一个临近点为例子，权重3的节点权重为3，dist[v]=3，权重3节点到临近第一个节点的权重为length(v,u)=7，一样以dist[v] + length(v,u)方式计算，得到原点经过权重3节点到权重3临近的第一个节点权重(成本)为10，权重3临近的另一个节点同样以这个方式计算。
以这个流程最后得到原点到各个顶点的最短距离路线为下图所示
C++代码实现
下面我们以C++代码实现该算法，不过这里我们用以网格图(8x8)来进行实现，原理过程都是一样的。
区别与伪码，我们以一个struct结构来省掉伪码中需要的一些定义。
typedef struct _vertoceNode
{
unsigned short isObstacle; //表示该顶点是否是障碍物
unsigned short visited; //表示该顶点是否被访问过
size_t row_index; //表示该顶点在二维数组中的竖下标位置
size_t col_index; //表示该顶点在二维数组中的横下标位置
size_t distance; //表示原点到该顶点的权重(距离成本)
_vertoceNode *pervNode; //到该顶点最短距离的上一个顶点(可以以该字段反推出到一个具体顶点的最短访问路径)
char name[0]; //表示打印出来的字符
} VertoceNode;
定义一个二维数组表示该网格图结构，这里定义8 x 8的网格大小
#define COL_SIZE 8
#define ROW_SIZE 8
static VertoceNode* graph[ROW_SIZE][COL_SIZE];
我们还需要一个创建该顶点结构体的方法，这里我们以UINT_MAX宏来代表无穷大，方法定义如下
VertoceNode *createAndInitNode(size_t nameSize)
{
VertoceNode *node = (VertoceNode *)malloc(sizeof(VertoceNode) + nameSize);
if (node != NULL) {
node->isObstacle = IS_FALSE;
node->visited = IS_FALSE;
node->row_index = 0;
node->col_index = 0;
node->distance = UINT_MAX;
node->pervNode = NULL;
memcpy(node->name, STRL("-"));
}
return node;
}
然后我们在定义一个初始化网格图结构的方法，该方法主要是初始化每个网格节点的顶点结构
void initGraph()
{
for (size_t i = 0; i < ROW_SIZE; i++)
{
for (size_t j = 0; j < COL_SIZE; j++)
{
VertoceNode *node = createAndInitNode(3);
if (node == NULL) {
printf("initGraph:call function[createAndInitNode(3)] error!\n");
exit(-1);
}
node->row_index = i;
node->col_index = j;
graph[i][j] = node;
}
}
}
为了最直观的体现最短路径，这里我们在网格中设置一些障碍物（用符号*表示），障碍物设置代码如下
void placeObstaclesToGraph()
{
graph[0][2]->isObstacle = IS_TRUE;
graph[0][3]->isObstacle = IS_TRUE;
graph[0][4]->isObstacle = IS_TRUE;
graph[0][5]->isObstacle = IS_TRUE;
graph[0][6]->isObstacle = IS_TRUE;
graph[0][7]->isObstacle = IS_TRUE;
graph[1][2]->isObstacle = IS_TRUE;
graph[2][2]->isObstacle = IS_TRUE;
graph[2][3]->isObstacle = IS_TRUE;
graph[2][4]->isObstacle = IS_TRUE;
graph[2][5]->isObstacle = IS_TRUE;
graph[2][6]->isObstacle = IS_TRUE;
graph[2][7]->isObstacle = IS_TRUE;
graph[1][7]->isObstacle = IS_TRUE;
graph[3][4]->isObstacle = IS_TRUE;
graph[3][5]->isObstacle = IS_TRUE;
}
当我们调用以上方法完成初始化后，打印出来的表格应该是这样（'-'为路，'*'为障碍物）
这个时候来实现我们的核心寻找最短路径算法，基本类似之前描述的伪码，整个核心算法的定义如下
size_t length(VertoceNode *v, VertoceNode *u)
{
//计算节点v到临近节点u的距离，因为生成的是网格图
//所以每个点到每个点的距离都是1
return v->distance + 1;
}
vector<VertoceNode *> *findShortestPath(VertoceNode *srcNode, VertoceNode *dstNode)
{
//初始化队列Q，并将所有顶点都添加到队列Q中
queue<VertoceNode *> q;
for (size_t i = 0; i < ROW_SIZE; i++)
{
for (size_t j = 0; j < COL_SIZE; j++)
{
VertoceNode *node = graph[i][j];
//如果是起点也就是原点，则距离初始化为0，上一个最短距离节点为NULL
//因为起点到起点本身的距离就是0，所以也就不存在上一个最短距离节点
if (i == srcNode->row_index && j == srcNode->col_index) {
node->distance = 0;
node->pervNode = NULL;
}
q.push(node);
}
}
//开始处理所有顶点
while (!q.empty())
{
VertoceNode *v = q.front();
q.pop();
//标识该顶点已经被访问过
v->visited = IS_TRUE;
//障碍物和未初始化的节点(因为存在障碍物，所以存在未初始化的节点)不参与寻路计算
if (IS_TRUE == v->isObstacle || v->distance == UINT_MAX) {
continue;
}
vector<VertoceNode *> *u = getVerticeNeighborList(v);
for (auto uNode = u->begin(); uNode != u->end(); uNode++) {
size_t alt = length(v, (*uNode));
if (alt < (*uNode)->distance) {
//找到最短距离
(*uNode)->distance = alt;
//记录最短距离的上一个节点
(*uNode)->pervNode = v;
}
}
delete u;
u = NULL;
}
....
}
之前的伪码有描述到，从队列q中得到一个顶点v后，要取到该v周围的顶点，并计算到达他们所需要的权重(成本)，如果小于他们现有的权重则代表找到最短距离并更新它们，查找V附近的顶点的代码实现如下:
vector<VertoceNode *> *getVerticeNeighborList(VertoceNode *node)
{
vector<VertoceNode *> *neighborList = new vector<VertoceNode *>();
//上方的的点
if (node->row_index > 0) {
VertoceNode *topNode = graph[node->row_index - 1][node->col_index];
if (IS_TRUE != topNode->isObstacle) {
neighborList->push_back(topNode);
}
}
//下方的点
if (node->row_index < ROW_SIZE - 1) {
VertoceNode *botNode = graph[node->row_index + 1][node->col_index];
if (IS_TRUE != botNode->isObstacle) {
neighborList->push_back(botNode);
}
}
//左边的点
if (node->col_index > 0) {
VertoceNode *leftNode = graph[node->row_index][node->col_index - 1];
if (IS_TRUE != leftNode->isObstacle) {
neighborList->push_back(leftNode);
}
}
//右边的点
if (node->col_index < COL_SIZE - 1) {
VertoceNode *rightNode = graph[node->row_index][node->col_index + 1];
if (IS_TRUE != rightNode->isObstacle) {
neighborList->push_back(rightNode);
}
}
return neighborList;
}
因为我们实现的时候用的是网格图(8x8)，所以一个点的周围有固定的四个顶点，也就是上下左右，我们需要考虑位置处于最顶端没有上方顶点以及处于最下端没有下方顶点等情况，当然周围的障碍物是不算在里面的，上面的实现逻辑应该能很清楚的表明这个处理过程。
下面详细讲解一下核心处理逻辑一些可能不明白的地方，整体逻辑与伪码实现是差不多的，首先从队列里面取出一个顶点v，然后从队列中删除它，并标记它为已访问，因为障碍物是不能到达以及寻路的，所以这里不参与下面的逻辑，那么后面的v->distance == UINT_MAX条件又是具体做什么的，因为我们是从原点开始初始化原点或者更新原点周围顶点的权重，并重复这个过程直到所有顶点都更新了权重也就得到了原点到所有顶点的最短距离，那么，考虑有障碍物的这种情况:
以这一行为例子，因为是网格图，一个节点的更新肯定是由它周围的节点进行的，也就是[3][1]是由它周围的比如[3][0]、[3][2]、[2][1]或者[4][1]来进行初始化或者更新，具体更新的值取决于谁更小(最短距离)，所以，我们来看[3][3]，因为[3][4]是障碍物，所以没有继续初始化它右边开始的节点，也就是[3][6]和[3][7]都是无穷大状态未被初始化为具体的权重值，如果这个时候[3][6]由[4][6]进行初始化，那么以上面的逻辑，在length(v, u)计算两个顶点之间的权重(成本)时，会让我们的无穷大代表值UINT_MAX + 1，因为我们的结构体的distance成员是size_t类型，这是一个无符号类型，也就是这个类型的最大值+1会造成溢出变成0(因为无符号)，这样这个distance本来是表示最短距离的成员，因为溢出被赋值为0，导致后面无法正确计算最短路径。所以这里不处理节点是无穷大的，让后面的逻辑以它周围的节点去更新它们。
当整个逻辑完成后，各个顶点结构的distance字段代表了原点到各个顶点的最短距离，那么，我们不仅想知道这个最短距离值，还想知道最短距离路径怎么办？值我们已经得到了，最短路径我们将利用我们顶点结构体里面的pervNode成员来完成。
我们在更新最短距离的时候，会把这个最短距离相关联的顶点更新到成员pervNode中，也就是说，pervNode成员代表了原点到该节点的最短距离中要通过的节点之一，一直到原点，pervNode为NULL，我们利用这个不断反推出完成的路径，逻辑如下:
//将到目标点的最短路径添加到一个容器中返回
vector<VertoceNode *> *shortestPathList = new vector<VertoceNode *>();
VertoceNode *iterNode = dstNode;
while (iterNode != NULL)
{
shortestPathList->push_back(iterNode);
iterNode = iterNode->pervNode;
}
reverse(shortestPathList->begin(), shortestPathList->end());
dstNode是我们想知道的最短路径的终点，因为前面的逻辑处理后，所有的顶点成员都已经是就绪状态(已经是原点到顶点的最短距离相关值)了，所以我们通过二维数组取出终点节点，利用它按照我们上述逻辑进行反推，并全部添加到一个list中，因为反推后是一个反方向的路径(终点 -> 起点)，所以当整体路径得到后，我们利用C++标准库的反转方法reverse，把这个包含路径的list反转一下，这个时候列表就是正确的(起点->终点)的顺序了。
最终目标效果如下，起点:S([0][0]) 终点:D([7][7]) 路:- 障碍物:*
完整代码实现:https://github.com/ZhiyangLeeCN/algorithms/blob/master/Dijkstra's%20Algorithm/main.cpp
参考文档:
https://brilliant.org/wiki/dijkstras-short-path-finder/
https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
by zhiyanglee | email:zhiyanglee@foxmail.com
网友评论