最短路--Dijkstra

Dijkstra是单源最短路算法,用于求正权图源点到每个顶点的最短路。Dijkstra用到了一些BFS的思想

算法步骤

  1. 初始化dis数组和vis数组。
    1. dis[i]表示源点到第i个点的距离,初始化为INF,表示无穷大。(INF为自己定义)
    2. vis[i]数组表示第i个点的最短路是否用于处理过未求出最短路的点。(当用优先队列的时候则不用vis数组)
  2. 找出当前最短dis[i],并且vis[i]为false的点。如果找不到,则最短路求解完成,算法结束。
  3. 令vis[i]为true,表示已经使用过该最短路处理其dis[i],防止重复使用。依次遍历其余所有点,令dis[j] = min(dis[j], dis[i]+w[i] [j])
    1. w[i] [j]表示点i到点j的距离。这一步表示源点到i加上ij的距离和源点到j的距离哪个小。

img

算法实现

邻接矩阵版

时间复杂度为O(n*n) n为顶点数

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
void dijkstra(int n, int s)//1.
{
for(int i=0; i<n; i++)//2.
{
dis[i] = w[s][i];
vis[i] = false;
}
dis[s] = 0;

for(int i=0; i<n; i++)//3.
{
int mn = INF, x;
for(int j=0; j<n; j++)//4.
if(!vis[j] && dis[j]<mn)
{
mn = dis[j];
x=j;
}

if(mn==INF)//5.
return;

vis[x] = true;//6.
for(int j=0; j<n; j++)
dis[j] = min(dis[j], dis[x]+w[x][j]);
}
}

注释:

  1. n为结点个数,s为源点。
  2. 初始化dis数组和vis数组
  3. 依次遍历每个结点
  4. 找出当先未使用过的最短路,并把下标存入x
  5. 如果全部使用过则算法结束
  6. vis[x]设为true,比较dis[j]和dis[x]+w[x] [j]的大小

优先队列版

用优先队列优化dijkstra大部分时间优于普通版,但是在完全图时普通版更好。

时间复杂度:O((m+n)logm) 其中n为顶点数,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
38
39
40
41
int dis[maxn];
vector<pair<int, int> > G[maxn];//1.

void add_eage(int s, int t, int w)
{
G[s].push_back(make_pair(w, t));//2.
G[t].push_back(make_pair(w, s));//3.
}
void init(int n)//4.
{
for(int i=0; i<n; i++)
G[i].clear();
}


void dijkstra(int n, int s)
{
for(int i=0; i<n; i++)//5.
dis[i] = (i==s)?0:INF;

priority_queue<pair<int, int>,
vector<pair<int, int> >,
greater<pair<int, int> > > q;//6.
q.push(make_pair(dis[s], s));//7.
while(!q.empty())
{
pair<int, int> p = q.top();
int x = p.second;//8.
q.pop();

for(int i=0; i<G[x].size(); i++)
{
int y=G[x][i].second, w=G[x][i].first;//9.
if(dis[x]+w<dis[y])//10.
{
dis[y] = dis[x]+w;
q.push(make_pair(dis[y], y));
}
}
}
}

注释:

  1. 存放pair的vector用来存放边和边权,因为pair比较大小是first优先,所以pair的first放的是权重。G[i] [j]存放的是和结点i相连的第j条边。G[i] [j].second存放的是和结点i相连的第j条边的另一个端点。G[i] [j].first存放的是和结点i相连的第j条边的权重。maxn为自己定义的常量。
  2. 将边添加至vector中,s、w、t 说明同上。
  3. 无向图的边是无向的,所以需要在G[s]和G[w]中都加入一条边。有向图不需要这一步。
  4. 初始化vector,清空所有先前加入的边。
  5. 初始化dis数组,将源点到源点的距离设置为0,其他的设置为INF(自己定义)。
  6. 定义优先队列,第一个参数为数据类型,比较pair类型,pair的first优先。第二个参数为存储容器,和先前存边的vector定义相同。第三个参数表示小顶堆(greater为小顶堆,less为大顶堆)。
  7. 将源点压入队列。
  8. x存放当前未访问过的权值最小边的一端结点编号。
  9. 依次遍历与x相连的边,y表示与x相连的边的另一端结点编号。w表示x到y路径权重
  10. 该步骤通邻接矩阵dijkstra相似

模板例题

hdoj1874

参考

  1. 夜深人静写算法(四)- 最短路和差分约束
  2. dijkstra几大模板(这里面的优先队列模板好像时错的,我只参考了他的stl用法)
  3. C++ pair的比较大小
Donate comment here