单源最短路径算法

算法流程：

对于图G（V，E）维护一个集合S,存放已经被访问过的顶点（准备期间只有源点s），每次从集合V-S中选择与起点s的距离最小的一个顶点（记为u），访问u并加入集合S，并令u为中介点，更新起点s与所有从u能达到的顶点v之间的最短距离。这样执行n次（n为顶点个数），直到集合S包含所有顶点。

算法书上的图

适用范围：有向无负权图

1.优先队列版 复杂度O(ElogE)

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define INF 0x3f3f3f3f

struct qnode{
    int v,d;
    qnode(int _v=0,int _d=0):v(_v),d(_d){}
    friend bool operator <(const qnode &r)const{
        return d>r.d;
    }
};

struct Edge{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
 
const int MAXN = 100010;
vector<Edge> E[MAXN];
//是否访问标志
int vis[MAXN];
//到源点的最短距离，准备期间设置为无穷大，表示不可及。
int dis[MAXN]; 
//加边
void add_edge(int u,int v,int w){
    E[u].push_back(Edge(v,w));
}
//初始化(从0开始编号)
void init(int n){
    for(int i=0;i<n;i++){
        E[i].clear();
    }
}

void Dijkstra(int s,int n){
    for(int i=0;i<n;i++)vis[i] = 0;
    for(int i=0;i<n;i++)dis[i] = (i == s ? 0 : INF);
    priority_queue<qnode> q;//声明优先队列：每次从队列中取出的是具有最高优先权的元素。
    //优先队列第一个参数为比较类型，第二个为容器类型，第三个为比较函数。
	//greater实现小顶堆//less 实现大顶堆（默认为大顶堆）
	q.push(qnode(s,dis[s]));//先将源点推进优先队列
	qnode temp;
    while(!q.empty()){//当队列空时所有边已被访问
        temp = q.top();q.pop();
        //当前顶点
        int u = temp.v;
        if(vis[u])continue;
        vis[u] = true;
        //每一条与u相邻的边都要更新
        for(int i=0;i<E[u].size();i++){
            //邻点
            int v = E[u][i].v;
            //权重
            int cost = E[u][i].cost;
            //松弛操作，更新权重时机
            if(!vis[v] && dis[u] + cost < dis[v]){
                dis[v] = dis[u] + cost;
                //把每一个更新的长度加进队列
                q.push(qnode(v,dis[v]));
            }
        }
    }
}

2.邻接矩阵版 复杂度O(N^2) 记录路径版

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
42
43
44
45
46
47
48
49
50
51
52
53
const int MAXN = 10000;
const int INF = 0x3f3f3f3f;
bool vis[MAXN];//访问记录
int pre[MAXN];//父节点
int cost[MAXN][MAXN];//权重矩阵
int lowcost[MAXN];//记录最短路径

//初始化矩阵为无穷。
void Init(int N){
    for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cost[i][j] = INF;
		}
	}
	//如果INF是满十六进制表示。如：const int INF = 0x3f3f3f3f;
	//则可以使用memset(cost,INF,sizeof(cost));
}

//cost:权重矩阵,lowcost:最短路径，n:数据范围,beg:源点
void Dijkstra(int cost[][MAXN],int lowcost[],int n,int beg){
	//初始化各值
	for(int i = 0; i < n; i++){
		lowcost[i] = INF;
		vis[i] = false;
		pre[i] = -1;
	}
	//设置源点
	lowcost[beg] = 0;
	for(int j = 0; j < n; j++){
		int k = -1;
		int Min = INF;
		//找到目前最短路径数组中到源点最短的节点。
		for(int i = 0; i < n; i++){
			if(!vis[i] && lowcost[i] < Min){
				Min = lowcost[i];
				k = i;
			}
		}
		//找不到，说明节点都已经全部访问。
		if(k == -1)break;
		//记录该节点。
		vis[k] = true;
		//松弛操作。更新每条与该节点相连并且还未访问到的节点的路径。
		for(int i = 0; i < n; i++){
			if(!vis[i] && lowcost[k] + cost[k][i] < lowcost[i]){
			    //发现一条更短的路径，更新。
				lowcost[i] = lowcost[k] + cost[k][i];
				//更新父节点。
				pre[i] = k;
			}
		}
	}
}

解题通用思路

做关于Dijkstra算法的题，通常不会只出一个裸的寻找最短路径，而是会给出一个或多个次级标尺。通常不会超出三个维度：

  • 边权
  • 点权
  • 多少条最短路径，或该路径的长度。

通常是多个维度组合起来寻找最优解。

遇到这类问题，可通过将每条最短路径都保存下来，依次进行处理。

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
vector<int> paths[MAXN];
//在其松弛操作中，将路径保存
for(int j = 0; j < N; j++){
	if(!vis[j] && G[k][j] != INF){
		if(dis[j] > dis[k] + G[k][j]){
			dis[j] = dis[k] + G[k][j];
			paths[j].clear();
			paths[j].push_back(k);
		}else if(dis[j] == dis[k] + G[k][j]){
			paths[j].push_back(k);
		}
	}
}
vector<vector<int> > ans;//用于存放每一个最短路径
vector<int> p;
//计算每条路径，注意，这样的路径是反序并且不包含源点的，如需要，则单独计算。
void makeMinPath(vector<vector<int> > &ans,vector<int> p,int j){
	if(j == 0){
		ans.push_back(p);
		return;
	}
	for(int i = 0; i < paths[j].size(); i++){
		p.push_back(paths[j][i]);
		makeMinPath(ans,p,paths[j][i]);
		p.pop_back();
	}
}

之后就可以根据要求计算每一条路径，并挑出符合问题的解了。