最短路

Posted on In

最短路

Floyd

定义数组f[k][x][y]，表示只允许经过1到k时x到y的最短路长度。

1
2
3
4
5
6
7
for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
    }
  }
}

然而时间复杂度为 \(O(n^3)\)。

Dijkstra

只能解决非负权图。

将结点分为两个集合：已经确定最短路长度的集合，和未确定的集合。

初始化 \(dis[start]=0\)，其他为 \(+\infty\)

随后重复：

  1. 取出未确定的集合中最短路长度最小的结点加入到确定的集合中
  2. 更新结点的最短路长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dijkstra(){
    memset(dis, INT_MAX, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[start] = 0;
    for(int i = 1; i <= n; i++){
        int mindis = INT_MAX;
        int pos = 0;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && dis[j] < mindis){
                pos = j;
                mindis = dis[j];
            }
        }
        if(pos != 0){
            vis[pos] = 1;
            for(int j = 1; j <= n; j++){
                dis[j] = min(dis[j], dis[pos] + graph[pos][j]);
            }
        }
    }
}

还可以使用优先队列，时间复杂度为 \(O(m\log m)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct node{
    int dis;
    int u;
    bool operator>(const node& a){
        return dis > a.dis;
    }
};

void dijkstra(){
    memset(dis, INT_MAX, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[start] = 0;
    std::priority_queue<node, vector<node>, greater<node>> q;
    int d = 0;
    node nd;
    nd.dis = 0;
    nd.u = start;
    q.push(nd);
    while(!q.empty()){
        int u = q.top().u;
        q.pop();
        if(vis[u]){
            continue;
        }
        vis[u] = 1;
        for(int i = 1; i <= n; i++){
            if(dis[i] > dis[u] + graph[u][i]){
                dis[i] = dis[u] + graph[u][i];
                node tmp;
                tmp.u = i;
                tmp.dis = dis[i];
                q.push(tmp);
            }
        }
    }
}