Dijkstra algorithm

2018/08/15 ALGO

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

单源最短路径问题

单源最短路径问题描述的是,求解在带权连通图中从起点s到终点t所经过的路径的耗费之和为最小。Dijkstra算法能够解决单源最短路径问题,它要求图中不含负权的边。

Dijkstra算法使用贪心的策略,声明一个数组dist保存起点s到其余所有点的最短距离,以及找到最短距离的点的集合T。算法开始时,dist数组初始化为INF无穷大(∞),dist[s]赋值为0。

紧接着,对于节点s能抵达的节点m,进行松弛操作更新dist数组,然后在dist数组中找到其中最小值,其对应的节点将加入集合T中,表明该节点已经找到最短路径。

松弛操作的伪代码如下,其中u、v是某条边的两个端点,w是这条边的耗费:

if dist[u] + w < dist[v]
    dist[v] = dist[u] + w;

上图中,dijkstra在运作的过程中,维护两个点的集合。一个是前面提到的集合T,它们都是已经找到了最短路径,而另一个集合则是G-T,也就是剩下的节点,它们还没被求解最短路径。

dijkstra的算法路径

给出下图:

下面是dijkstra的算法路径。

  1. 首先节点0开始有两条边,松弛操作后distTo更新节点2、节点4。
  2. 将节点2添加到集合T,然后更新2-7,此时distTo更新节点7。
  3. distTo中最小值、并且不在集合T的是节点4,更新4-5、4-7。其中4-7的边松弛失败,不予更新节点7。
  4. 以此类推。

改进

上述的dijkstra算法使用的dist数组,每次都要在其中找到最小值然后添加到集合T。那么我们可以使用最小堆来加快找最小值的速度。实现最小堆的常用数据结构是最小优先队列。

下面是使用最小优先队列的C实现:

const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;
struct qnode{
    int v;
    int c;
    qnode(int _v = 0, int _c = 0):v(_v),c(_c){}
    bool operator < (const qnode &r)const{
        return c>r.c;
    }
};

struct Edge{
    int v, cost;
    Edge(int _v = 0, int _cost = 0):v(_v),cost(_cost){}
};

void addedge(int u, int v, int w){
    E[u].push_back(Edge(v, w));
}

vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n, int start){
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++){
        dist[i] = INF;
    }
    priority_queue<qnode>que;
    while(!que.empty()){
        que.pop();
    }
    dist[start] = 0;
    que.push(qnode(start, 0));
    qnode tmp;
    while(!que.empty()){
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if(vis[u]){
            continue;
        }
        vis[u] = true;
        for(int i=0;i<E[u].size();i++){
            int v = E[tmp.v][i].v;
            int cost = E[u][i].cost;
            if(!vis[v] && dist[v] > dist[u] + cost){
                dist[v] = dist[u] + cost;
                que.push(qnode(v, dist[v]));
            }
        }
    }
}

Search

    Table of Contents