博客

带权图

在图中，给每一条路径带上一定的权重，这样的图我们称为带权图。如下图所示：



我们现在来回顾一下BFS跟DFS的基本思想：

• 深度优先搜索：继续沿着路径搜索，直到我们需要回溯，但这种方式不保证最短路径。

• 广度优先搜索：查看包含距离1的邻居，然后是距离2的邻居等的路径，直到找到路径，这种方式保证最短路径。

但这两种方法都是无法处理带权图的问题。举个例子



由A到D的最短路径是什么？我们当然会毫不犹豫得回答，A->D。是的，确实是A到D。但是如果是这样的带权图（即数字代表两个节点之间的距离）呢？



A->D还是最短路径吗？显然不是。应该是abc，因为三者的权重值加起来都不如ad的权重。所以用B(D)FS是无法找到最短路径的。

尽管我们知道BFS算法保证了两个节点中的最短距离，但是在带权图中，两个节点间的最小花费值才是最短路径。

Dijstra’s Algorithm

回想一下我们之前是怎么实现BFS算法的。如果我们使用BFS来查找路径（忽略权重），我们将使用队列来存储每个路径。类似于这种做法，我们可以利用一种优先队列来实现这种算法。这种算法称为“Dijkstra算法”，他使用优先级队列来对每条路径进行排队。

我们先来对比一下两种算法的伪代码：

BFS伪代码

bfs from v1 to v2:
	//建立一个队列q来存储走过的路径path（可以用vector来存储路径）
    create a queue of paths (a vector), q
    //将节点v1的路径入队
    q.enqueue(v1 path)
    //当q不为空，并且节点V2未被访问时
    while q is not empty and v2 is not yet visited:
    //将q中的元素移出队列，并且存入path中
        path = q.dequeue()
        //将路径中的最后元素赋值给节点型变量v
        v = last element in path
        //如果v未被访问
        if v is not visited:
        //标记节点V
        mark v as visited
        //如果节点是目标节点，停止执行
        if v is the end vertex, we can stop.
        //遍历V中所有未被标记的邻居
        for each unvisited neighbor of v:
        //将v节点的邻居作为最后的元素构成新的路径
             make new path with v's neighbor as last element
             //将新的路径排入队列中
             enqueue new path onto q 

Dijstra’s Algorithm算法的伪代码

bfs from v1 to v2:
    create a priority queue of paths (a vector), q //注意这里是 priority queue
    q.enqueue(v1 path)
    while q is not empty and v2 is not yet visited:
        path = q.dequeue()
        v = last element in path
        mark v as visited
        if v is the end vertex, we can stop.
       for each unvisited neighbor of v:
             make new path with v's neighbor as last 
                element
             enqueue new path onto q 

因为这种算法每次都是选择最小的花费路径，因此该算法我们又称为“贪婪算法”（“greedy” algorithm）

。现在我们就来分析一下下面这张带权图的最短路径及其权重值、

1. 从开始的节点（A）开始，在向下一级邻居移动之前，探索它的邻居节点（基于优先级）。

Vector<Vertex  *> startPath
	startPath.add(A,0)  //从节点A开始，权重为0
	pq.enqueue(startPath) //将初始的路径存入优先级队列中

此时优先级队列的内容为：



已标记的点的集合为空：

2. 接下来执行while循环里面的语句：

in while loop:
//将当前队列的内容取出
   curPath = pq.dequeue() (path is A, priority is 0)
   //将路径中的最后一个元素赋值给节点变量V
   v = last element in curPath (v is A)
   //标记变量V
   mark v as visited
   //将所有未访问的邻居路径排入q，并根据新的边长度更新优先级
   enqueue all unvisited neighbor paths onto q, 
   with updated priorities based on new edge length

此时优先级队列的状态为：



已访问的集合为：

3. 此时队列不为空，继续执行while语句内的内容，具体内容变化如下：

in while loop:
//出队列，现在AD排在队头，因此出去的为路径AD，优先级为3
   curPath = pq.dequeue() (path is AD, priority is 3)
   //该路径中最后的一个元素为D，并赋值给节点元素
   v = last element in curPath (v is D)
   //标记节点V
   mark v as visited
   将所有未访问的邻居路径排入q，并根据新的边长度更新优先级
   enqueue all unvisited neighbor paths onto q, 
   with updated priorities based on new edge length

此时优先级队列的内容为



即此时D的邻居节点为G和E，由于W（A-> D -> E）= 3+1 = 4 < W(AB) = 6.

因此ADE优先于AB，排在队头。已访问的节点如下

4. 我们继续分析，此时下一轮出队列的路径时ADE,路径尾元素是E，于是将E的节点的所有邻居路径添加进来：
   
   
   
   已访问的节点结合为：
   
   

5. 重复执行上述步骤，直到第一次V=I的出现。

6. 当V = I 的时候，表明存在一条路径使得A -> I.有队列的优先级可知，
   
   第一次出现的一定是权重总和最小的。（即开销最小的）
   
   。对于上述的例子最后的状态应该是这样的：

标记集合为



（此时已经没有可以入队的路径了，因为所有邻居节点都被访问过）。所以，最短的路径就是ADEHI，权重为13.

关于Edsger Dijkstra

计算历史Tidbit：Edsger Dijkstra

荷兰学者Edsger Dijkstra是计算机科学领域的另一个巨头。他是第一批称自己为“程序员”的科学家之一（他因此而几乎无法结婚！）他最初获得理论物理学学位，但在1950年初被电脑迷住了

Dijkstra在许多计算领域都具有极大的影响力：编译器，操作系统，并发编程，软件工程，编程语言，算法设计和教学（以及其他！）

很难确定哪些领域是他最着名的或者说最厉害的，因为他对CS的影响实在是太大了。

Dijkstra在使编程更具结构性方面也很有影响力 – 他撰写了一篇名为“Goto Considered Harmful”的开创性论文（GOTO有害论），他抨击了“goto”声明的概念（存在于C ++中 ，现在几乎不怎么用到，如果有机会的话，就使用一下试试它！）

其中更酷的是，字母“ijk”在他的名字中是相邻的（这就是为什么我们在循环中使用i，j，k？）。他的早期论文都是是手写的，他的笔迹很漂亮。这个字体是“Edsger Dijkstra”字体！