图论-单源最短路径（Dijskal算法）

浅浅的花香味﹌ 2022-12-09 05:18 246阅读 0赞

### 文章目录 ###

*  Dijkstra
 *  原理
 *  模板
 *  例题
 *   *  HDU-2544 最短路
     *  HDU-2680 Choose the best route
     *  POJ-1062 昂贵的聘礼
     *  POJ-1511 Invitation Cards

# Dijkstra #

--------------------

Dijkstra算法是图论中用来求单源最短路径的经典算法，复杂度可以优化到 O ( m l o g ( n ) ) O(mlog(n)) O(mlog(n))。从整体上看就是从一个起点，扩散到整个图的过程。  
打个比方，把图的边看成多米诺骨牌，骨牌数量和边的权值成正比，假设骨牌倒下速度一样，从起点推倒骨牌，所连边上的骨牌都倒下，到达所有能到达的终点。并且某个结点先倒下来的骨牌就是最短路径，后倒过来的骨牌对最短路径没有贡献，忽略之。

# 原理 #

--------------------

Dijkstra算法应用了贪心的思想，即“抄近路走”。维护两个集合 A A A和 B B B， A A A表示已确定最短路径的结点集（红色表示）， B B B表示邻居结点（蓝色表示）。  
![在这里插入图片描述][20201002104904617.png_pic_center]

1.  首先把起点1放入 A A A中，把它的所有邻居放入 B B B中  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]
2.  在 B B B中找距离起点最短的结点放入 A A A中，即结点3，并把它的邻居加入进 B B B，距离是起点到该节点的距离+该节点到邻居的距离。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 1]
3.  此时 B B B中存在相同结点2，我们取距离更短的那个，即舍弃(2,5)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 2]
4.  以此类推，把 B B B中距离最短的结点2放入 A A A中，加入邻居，然后舍弃更远的(4,7)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 3]
5.  最后得到起点到其他结点的最短路径  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 4]  
    上述方法中，对于每次寻找 B B B中距离最近结点，可以用优先队列实现，这样依赖复杂度就能优化到 O ( m l o g ( n ) ) O(mlog(n)) O(mlog(n))。  
    如果要打印路径，定义一个数组 p r e \[ \] pre\[\] pre\[\]记录前驱结点就好了，也就是它是作为谁的邻居进入 B B B中的，然后递归打印。

# 模板 #

--------------------

struct edge {   //边
    	int from, to, w;  //起点，终点，权值
    	edge(int a, int b, int c) { 
    		from = a, to = b, w = c;
    	}
    };
    struct node { 
    	int id, dis; //即图解中的(结点，距离)
    	node(int a, int b) { 
    		id = a, dis = b;
    	}
    	bool operator< (const node &a)const { 
    		return a.dis < dis;
    	}
    };
    int n, m, x, y, z;
    vector<edge>e[maxn];  //邻接表存图
    int dis[maxn], pre[maxn]; //记录最短路径和 前驱节点
    bool vis[maxn];  //记录是否已入A，实现舍弃操作
    void print_path(int s, int t) {  //打印起点s到点t最短路径
    	if (s == t)return;
    	print_path(s, pre[t]);
    	printf("%d ", t);
    }
    void dijkstra(int s) {  //传入起点
    	memset(dis, inf, sizeof(dis));
    	memset(vis, false, sizeof(vis));
    	dis[s] = 0;
    	priority_queue<node>q;  //优先队列
    	q.push(node(s, dis[s]));  //入队起点
    	while (!q.empty()) { 
    		node cur = q.top();
    		q.pop();
    		if (vis[cur.id])continue;
    		vis[cur.id] = true;  //即已找到最短路径
    		for (int i = 0; i < e[cur.id].size(); i++) {   //检查所有邻居
    			edge nex = e[cur.id][i];
    			if (vis[nex.to])continue;  //舍弃(更优的已经get)
    			if (dis[nex.to] > nex.w + cur.dis) {  //扩展新邻居
    				dis[nex.to] = nex.w + cur.dis;
    				q.push(node(nex.to, dis[nex.to]));
    				//pre[nex.to] = cur.id; //记录路径
    			}
    		}
    	}
    }

# 例题 #

--------------------

## HDU-2544 最短路 ##

[HDU-2544 最短路][HDU-2544]

> **Problem Description**  
> 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？  
> **Input**  
> 输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。  
> 输入保证至少存在1条商店到赛场的路线。  
> Output  
> 对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间  
> **Sample Input**  
> 2 1  
> 1 2 3  
> 3 3  
> 1 2 5  
> 2 3 5  
> 3 1 2  
> 0 0  
> **Sample Output**  
> 3  
> 2

**分析**：模板题

#include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn = 102;
    struct edge {  
    	int from, to, w;
    	edge(int a, int b, int c) { 
    		from = a, to = b, w = c;
    	}
    };
    struct node { 
    	int id, dis;
    	node(int a, int b) { 
    		id = a, dis = b;
    	}
    	bool operator< (const node &a)const { 
    		return a.dis < dis;
    	}
    };
    int n, m, x, y, z;
    vector<edge>e[maxn];  
    int dis[maxn];
    bool vis[maxn];  
    void dijkstra(int s) { 
    	dis[s] = 0;
    	priority_queue<node>q; 
    	q.push(node(s, dis[s])); 
    	while (!q.empty()) { 
    		node cur = q.top();
    		q.pop();
    		if (vis[cur.id])continue;
    		vis[cur.id] = true; 
    		for (int i = 0; i < e[cur.id].size(); i++) {   
    			edge nex = e[cur.id][i];
    			if (vis[nex.to])continue;  
    			if (dis[nex.to] > nex.w + cur.dis) { 
    				dis[nex.to] = nex.w + cur.dis;
    				q.push(node(nex.to, dis[nex.to]));
    			}
    		}
    	}
    }
    int main() { 
    	while (~scanf("%d%d", &n, &m)) { 
    		if (n == 0 && m == 0)break;
    		for (int i = 1; i <= n; i++)e[i].clear();
    		memset(dis, inf, sizeof(dis));
    		memset(vis, false, sizeof(vis));
    		while (m--) { 
    			scanf("%d%d%d", &x, &y, &z);
    			e[x].push_back(edge(x, y, z));
    			e[y].push_back(edge(y, x, z));
    		}
    		dijkstra(1);
    		printf("%d\n", dis[n]);
    	}
    	return 0;
    }

## HDU-2680 Choose the best route ##

[HDU-2680 Choose the best route][]

> **Problem Description**  
> One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.  
> **Input**  
> There are several test cases.  
> Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.  
> Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .  
> Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.  
> **Output**  
> The output contains one line for each data set : the least time Kiki needs to spend ,if it’s impossible to find such a route ,just output “-1”.  
> **Sample Input**  
> 5 8 5  
> 1 2 2  
> 1 5 3  
> 1 3 4  
> 2 4 7  
> 2 5 6  
> 2 3 5  
> 3 5 1  
> 4 5 1  
> 2  
> 2 3  
> 4 3 4  
> 1 2 3  
> 1 3 4  
> 2 3 2  
> 1  
> 1  
> **Sample Output**  
> 1  
> \-1

**分析**：  
站台编号1~n，假设起点是0(超级源点)，那么可以直接出发的点置距离为0，然后套算法即可。

#include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn = 1003;
    struct node { 
    	int id, dis;
    	node(int a, int b) { 
    		id = a, dis = b;
    	}
    	bool operator <(const node& a)const { 
    		return a.dis < dis;
    	}
    };
    int mp[maxn][maxn], dis[maxn];
    bool vis[maxn];
    int n, m, e, x, y, z;
    void dijkstra() { 
    	dis[0] = 0;
    	priority_queue<node>q;
    	q.push(node(0, dis[0]));
    	while (!q.empty()) { 
    		node cur = q.top();
    		q.pop();
    		if (vis[cur.id])continue;
    		vis[cur.id] = true;
    		for (int i = 0; i <= n; i++) { 
    			if (mp[cur.id][i] == inf)continue; //无路
    			if (vis[i])continue;
    			if (dis[i] > mp[cur.id][i] + cur.dis) { 
    				dis[i] = mp[cur.id][i] + cur.dis;
    				q.push(node(i, dis[i]));
    			}
    		}
    	}
    }
    int main() { 
    	while (~scanf("%d%d%d", &n, &m, &e)) { 
    		memset(mp, inf, sizeof(mp));
    		memset(dis, inf, sizeof(dis));
    		memset(vis, false, sizeof(vis));
    		while (m--) { 
    			scanf("%d%d%d", &x, &y, &z);
    			if (z < mp[x][y])  //重边
    				mp[x][y] = z;
    		}
    		scanf("%d", &x);
    		while (x--) {  //置距起点为0
    			scanf("%d", &y);
    			mp[0][y] = 0;
    		}
    		dijkstra();
    		if (dis[e] == inf)puts("-1");
    		else printf("%d\n", dis[e]);
    	}
    	return 0;
    }

> （插播反爬信息 ）博主CSDN地址：[https://wzlodq.blog.csdn.net][https_wzlodq.blog.csdn.net]

## POJ-1062 昂贵的聘礼 ##

[POJ-1062 昂贵的聘礼][POJ-1062]

> **Problem Description**  
> 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：“嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。“探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。  
> 为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。  
> **Input**  
> 输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和"优惠价格”。  
> **Output**  
> 输出最少需要的金币数。  
> **Sample Input**  
> 1 4  
> 10000 3 2  
> 2 8000  
> 3 5000  
> 1000 2 1  
> 4 200  
> 3000 2 1  
> 4 200  
> 50 2 0  
> **Sample Output**  
> 5250

**分析**：  
把物品看作图上的结点，互换关系看作边，求最小花费也就是从起点到某一点的最短路径。不过还需处理等级限制，只需要枚举等级区间，每次对满足区间的点做dijkstra()即可。  
比如起点等级是5，限制是3，那么枚举的区间有\[2,5\]、\[3,6\]、\[4,7\]、\[5,8\]详见代码。

#include<cstdio>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn = 102;
    struct node { 
    	int id, dis;
    	node(int a, int b) { 
    		id = a, dis = b;
    	}
    	bool operator<(const node& a)const { 
    		return a.dis < dis;
    	}
    };
    int n, m, x, y, z;
    int mp[maxn][maxn], dis[maxn];
    int lev[maxn], val[maxn];
    bool tag[maxn], vis[maxn];
    int dijkstra() { 
    	memset(vis, false, sizeof(vis));
    	memset(dis, inf, sizeof(dis));
    	priority_queue<node>q;
    	dis[1] = 0;
    	q.push(node(1, dis[1]));
    	while (!q.empty()) { 
    		node cur = q.top();
    		q.pop();
    		if (vis[cur.id])continue;
    		vis[cur.id] = true;
    		for (int i = 1; i <= n; i++) { 
    			if (vis[i] || !tag[i])continue; //多一个判断：是否在枚举区间内
    			if (dis[i] > mp[cur.id][i] + cur.dis) { 
    				dis[i] = mp[cur.id][i] + cur.dis;
    				q.push(node(i, dis[i]));
    			}
    		}
    	}
    	int rtn = inf;
    	for (int i = 1; i <= n; i++) 
    		if (rtn > dis[i] + val[i])  //记得加上结点权值
    			rtn = dis[i] + val[i];
    	return rtn;
    }
    int main() { 
    	scanf("%d%d", &m, &n);
    	memset(mp, inf, sizeof(mp));
    	for (int i = 1; i <= n; i++) { 
    		scanf("%d%d%d", &val[i], &lev[i], &x);
    		while (x--) { 
    			scanf("%d%d", &y, &z);
    			mp[i][y] = z;
    		}
    	}
    	int ans = inf;
    	for (int i = 0; i <= m; i++) { 
    		memset(tag, false, sizeof(tag));
    		for (int j = 1; j <= n; j++) {   //枚举
    			if (lev[1] - m + i <= lev[j] && lev[1] + i >= lev[j])
    				tag[j] = true;
    		}
    		ans = min(ans, dijkstra());
    	}
    	printf("%d\n", ans);
    	return 0;
    }

## POJ-1511 Invitation Cards ##

[POJ-1511 Invitation Cards][]

> **Problem Description**  
> In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling by bus. A special course was taken where students learned how to influence people and what is the difference between influencing and robbery.  
> The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where ‘X’ denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.  
> All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.  
> **Input**  
> The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop.  
> **Output**  
> For each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.  
> **Sample Input**  
> 2  
> 2 2  
> 1 2 13  
> 2 1 33  
> 4 6  
> 1 2 10  
> 2 1 60  
> 1 3 20  
> 3 4 10  
> 2 4 5  
> 4 1 50  
> **Sample Output**  
> 46  
> 210

**分析**：  
n站点m条公交路线，只从起点到终点(单向)，求往返最小花费，来回往返两次，把来的单向路弄一次，再把路反过来弄一次就行了。  
注意数据较大用邻接矩阵和long long。

#include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    #define inf 0x3f3f3f3f
    typedef long long ll;
    const int maxn = 1000006;
    struct node { 
    	int id, dis;
    	node(int a, int b) { 
    		id = a, dis = b;
    	}
    	bool operator<(const node& a)const { 
    		return a.dis < dis;
    	}
    };
    struct edge { 
    	int from, to, w;
    	edge(int a, int b, int c) { 
    		from = a, to = b, w = c;
    	}
    };
    vector<edge>e[maxn];
    int t, n, m;
    int dis[maxn];
    int from[maxn], to[maxn], cost[maxn];
    bool vis[maxn];
    void dijkstra(int s) { 
    	memset(dis, inf, sizeof(dis));
    	memset(vis, false, sizeof(vis));
    	dis[s] = 0;
    	priority_queue<node>q;
    	q.push(node(s, dis[s]));
    	while (!q.empty()) { 
    		node cur = q.top();
    		q.pop();
    		if (vis[cur.id])continue;
    		vis[cur.id] = true;
    		for (int i = 0; i < e[cur.id].size(); i++) { 
    			edge nex = e[cur.id][i];
    			if (vis[nex.to])continue;
    			if (dis[nex.to] > cur.dis + nex.w) { 
    				dis[nex.to] = cur.dis + nex.w;
    				q.push(node(nex.to, dis[nex.to]));
    			}
    		}
    	}
    }
    int main() { 
    	scanf("%d", &t);
    	while (t--) { 
    		scanf("%d%d", &n, &m);
    		for (int i = 0; i <= n; i++)e[i].clear();
    		for (int i = 0; i < m; i++) { 
    			scanf("%d%d%d", &from[i], &to[i], &cost[i]);
    			e[from[i]].push_back(edge(from[i], to[i], cost[i]));
    		}
    		dijkstra(1);
    		ll ans = 0;
    		for (int i = 1; i <= n; i++)
    			ans += dis[i];
    		for (int i = 0; i <= n; i++)e[i].clear();
    		for (int i = 0; i < m; i++) //反转路的方向
    			e[to[i]].push_back(edge(to[i], from[i], cost[i]));
    		dijkstra(1);
    		for (int i = 1; i <= n; i++)
    			ans += dis[i];
    		printf("%lld\n", ans);
    	}
    	return 0;
    }

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://wzlodq.blog.csdn.net][https_wzlodq.blog.csdn.net]  
> *如果文章对你有帮助，记得一键三连❤*

[20201002104904617.png_pic_center]: /images/20221123/48e68decf04348bcb3ee26ee82664f86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e67958990f3c49c9b30a79ce128201dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/820e96ef09334015aab6bf262e54e6f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/afdd3df008254043b111d116072063f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/6fac47c2da3d4d1e9ec1ebdd3f59c86b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/59475b50d05a4c9181ef1b20228b4d65.png
[HDU-2544]: https://vjudge.net/problem/HDU-2544
[HDU-2680 Choose the best route]: https://vjudge.net/problem/HDU-2680
[https_wzlodq.blog.csdn.net]: https://wzlodq.blog.csdn.net
[POJ-1062]: https://vjudge.net/problem/POJ-1062
[POJ-1511 Invitation Cards]: https://vjudge.net/problem/POJ-1511