|
|
本文结构：
- 基础知识：邻接表
- dijkstra是用来干什么的？
- 算法原理
- 实战运用与代码实现
- 堆优化的Dijkstra算法
一、基础知识：邻接表
维基百科上的定义是这样的：
在图论中，邻接表代表一个图中的所有边或弧。
如果是无向图，那么每条边由两个结点组成，分别代表边的两个端点；如果是有向图，那么每条边是一个结点对，分别代表边的始点和终点。
在代码层面上，邻接表就是一个二维数组，数组的二维序号分别代表两个点，二表中保存的信息即这两个点之间的边的权。
当然，还有链表形式的邻接表：
如图所示，点1到点2的这条边在邻接表中可以表示为G[1][2]=2。
二、dijkstra是用来干什么的？
Dijkstra是河南（荷兰）著名科学家Edsger Wybe Dijkstra发明的著名算法，简单点来说，Dijkstra算法的作用是：解决单源最短路径问题。
用人话来说，假设有许多城市，城市之间的有许多条路线可走，比如城市A走到城市B，你既可以选择直接从A城市到B城市，也可以从A到B，再从B到C，还可以先从A到D，D到C，再从C到B等等。现在，你从一个城市出发，如何才能知道从这个城市到每个其它城市的最短距离呢？
三、算法原理
已知城市之间的路径长度，用邻接表G保存，要想知道从城市1到城市2、3、4的最短距离：
1、创建一个一维数组arr，对应序号中保存着城市1可以直接到达的城市的路径长度。
2、在数组中找到从与城市1路径最短且未访问的城市j，在邻接表边权重总是为正的情况下，这城市1与城市i之间的最短距离此时已经确定了arr，无法更短。此时标记城市i为已访问，并以该城市为中转站，以下面这个规则更新城市1到其他城市j的最短距离：
arr[j]=min(arr[j],arr+G[j]);
3、重复2直到所有城市都标记为止。
最后得到的arr[]中就是从城市1到其他几个城市的最短距离。
这个过程如图所示：
更详细的原理分析可参考链接：
算法 7：Dijkstra 最短路算法
四、实战运用与代码实现
练习一：
1072. Gas Station (30)
时间限制
200 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.
Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive integers: N (<= 103), the total number of houses; M (<= 10), the total number of the candidate locations for the gas stations; K (<= 104), the number of roads connecting the houses and the gas stations; and DS, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered from G1 to GM.
Then K lines follow, each describes a road in the format
P1 P2 Dist
where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.
Output Specification:
For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to 1 decimal place. If the solution does not exist, simply output “No Solution”.
Sample Input 1:4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
Sample Output 1:G1
2.0 3.3
Sample Input 2:2 1 2 10
1 G1 9
2 G1 20
Sample Output 2:No Solution 题意大概是一共有n个住处，m个加油站候选位置，另外有k条路连接着这n+m位置中的其中两个。需要你从m中选出一个最好的加油站位置x，要求x离其他n个的住处的最短路径的最小值要最大，同时最短路径的平均值要最小。
显然这是一个单源最短路经问题，妥妥地用dijkstra搞定。
AC代码+详细注释
#include<vector>
#include<iostream>
#include<string>
#include<climits>
#include<iomanip>
using namespace std;
int n,c,r,l;
int index(string s){//将Gi转换为相应的数字序号
int res=0;
if(s[0]==&#39;G&#39;){
res+=n;
res+=stoi(s.substr(1,(int)s.size()-1));
}else res+=stoi(s);
return res;
}
string gas(int index){//将Gas Station的数字序号转换为Gi
int res=index-n;
return &#34;G&#34;+to_string((long long)res);
}
void dijkstra(int now,vector<int>&ans,vector<vector<int>>&G){
vector<int>res(G[now]);//初始化第now个Gas Station离民宅的距离
vector<int>mark((int)res.size(),0);//民宅的访问标记
for(int i=1;i<(int)res.size();i++){
int minl=INT_MAX,minindex=now;
//找到距离该Gas Station最近的民宅
for(int j=1;j<(int)res.size();j++){
if(res[j]>0&&res[j]<minl&&mark[j]==0){
minl=res[j];
minindex=j;
}
}
mark[minindex]=1;//标记此最近的民宅为已访问
for(int j=1;j<(int)res.size();j++){
if(G[minindex][j]>0){//如果最近的民宅与民宅j存在路径
//如果j民宅与now号Gas Station未通
//则as Station与j号民宅的最短距离为G[minindex][j]+res[minindex]
//否则取G[minindex][j]+res[minindex]和res[j]的最小值
res[j]=(res[j]>0?min(res[j],G[minindex][j]+res[minindex]):G[minindex][j]+res[minindex]);
}
}
}
ans=res;//将结果传回ans
}
int main(){
//处理输入
cin>>n>>c>>r>>l;
vector<vector<int>>G(n+c+1,vector<int>(n+c+1,-1));
for(int i=0;i<r;i++ ){
string a,b;
int len;
cin>>a>>b>>len;
G[index(a)][index(b)]=len;
G[index(b)][index(a)]=len;
}
int best=-1;
double resave=INT_MAX,resminl=0;
for(int i=n+1;i<=n+c;i++){
vector<int>ans(n+c+1,INT_MAX);
double ave=0,minl=INT_MAX;
dijkstra(i,ans,G);
bool isok=true;
for(int i=1;i<=n;i++){
if(ans>l){
isok=false;
break;
}
ave+=ans;//路径长度累加
minl=min(minl,(double)ans);//找出路径极小值
}
ave/=n;//求平均值
//找出离民宅平均路径最短，但最小值最大的Gas Station
if(isok){
if(minl>resminl){
best=i;
resave=ave;
resminl=minl;
}else if(minl==resminl&&resave>ave){
best=i;
resave=ave;
resminl=minl;
}
}
}
//打印结果
if(best<0){
cout<<&#34;No Solution&#34;<<endl;
}else{
cout<<gas(best)<<endl;
cout<<fixed<<setprecision(1)<<resminl<<&#39; &#39;<<resave<<endl;
}
return 0;
}练习二：
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
Note: N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100. 典型的求单源头最小路径问题。同样的，使用dijkstra算法。
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
vector<vector<int>>G(N+1,vector<int>(N+1,-1));
for(int i=0;i<(int)times.size();i++){
G[times[0]][times[1]]=times[2];//生成邻接表
}
vector<int>mark(N+1,0);//网络节点访问标记
vector<int>len(G[K]);
for(int i=0;i<(int)len.size();i++){
int minlen=INT_MAX;
int minindex=0;
for(int j=0;j<(int)len.size();j++){
if(mark[j]==0&&len[j]>=0&&len[j]<minlen){
minlen=len[j];minindex=j;
}
}
mark[minindex]=1;//标记网络延时最短的节点
for(int j=0;j<(int)len.size();j++){
if(G[minindex][j]>=0)len[j]=len[j]==-1?len[minindex]+G[minindex][j]:min(len[j],len[minindex]+G[minindex][j]);
}
}
int res=INT_MIN;
for(int i=1;i<(int)len.size();i++){
if(i==K)continue;
if(len==-1)return -1;
res=max(res,len);
}
return res;
}
};思路基本与练习一相同。
提交结果：
练习三：
Given two words (beginWord and endWord), and a dictionary&#39;s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = &#34;hit&#34; endWord = &#34;cog&#34; wordList = [&#34;hot&#34;,&#34;dot&#34;,&#34;dog&#34;,&#34;lot&#34;,&#34;log&#34;,&#34;cog&#34;]
As one shortest transformation is &#34;hit&#34; -> &#34;hot&#34; -> &#34;dot&#34; -> &#34;dog&#34; -> &#34;cog&#34;,
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes. 虽然一眼望去就明白这是一道搜索题，用广度优先搜索、深度优先搜索应该都能出结果。不过既然是依旧是最短路径问题（点到点），不妨换个花样，看看Dijkstra是否能行。
这道题稍微复杂一些，首先得相办法利用字符串之间的关系生成一个邻接表。办法也很简单，将字符串和其在数组中的序号一一对应，如果两个字符串只有一个字符不同，那么在邻接表中，相应的格子就可以标记为1，表示两者的距离为1。具体实现代码如下：
class Solution {
public:
bool compare(string &a,string &b){//判定两个字符串是否只有一个字符不同
if(a.size()!=b.size())return false;
int diff=0;
for(int i=0;i<(int)a.size();i++){
if(a!=b)diff++;
}
return diff==1;
}
int ladderLength(string st, string end, vector<string>& wordlist) {
vector<vector<short>>G(wordlist.size()+1,vector<short>(wordlist.size()+1,0));
int sti=(wordlist.size()),endi=-1;//起始字符串不在数组中，放在邻接表的最后一行、一列
for(int i=0;i<(int)wordlist.size();i++){
if(wordlist==end){//寻找目标单词的序号
endi=i;
break;
}
}
if(endi==-1)return 0;//如果目标单词不存在，不可能有解，直接返回0；
for(int i=0;i<(int)wordlist.size();i++){//利用字符串之间的差异生成邻接表
if(compare(st,wordlist)){
G[sti]=1;G[sti]=1;
}
}
for(int i=0;i<(int)wordlist.size()-1;i++){
for(int j=i+1;j<(int)wordlist.size();j++){
if(compare(wordlist,wordlist[j])){
G[j]=1;G[j]=1;
}
}
}
//Dijkstra算法核心部分：
vector<short>len(G[sti]);//初始化各个单源最短路径
vector<short>mark(len.size(),0);//字符串的访问标记
for(int i=0;i<(int)len.size();i++){
int minn=INT_MAX;
int index=0;
for(int j=0;j<(int)len.size();j++){
if(mark[j]==0&&len[j]>0&&len[j]<minn){
minn=len[j];
index=j;
}
}
mark[index]=1;
for(int j=0;j<(int)G[index].size();j++){
if(G[index][j])len[j]=len[j]==0?len[index]+G[index][j]:min((int)len[index]+G[index][j],(int)len[j]);
}
}
return len[endi]==0?0:len[endi]+1;
}
};提交结果不是很理想，看样子这道题Dijkstra不是这道题最好的思路。
五、堆优化的Dijkstra算法
参考链接：[最短路]使用优先队列优化的Dijkstra算法 - CSDN博客
struct edge {int to,cost;};
typedef pair<int,int> P; //first是最短距离，second是顶点的编号
int V;//顶点个数
vector<edge> G[MAXV];
int d[MAXV];
void dijkstra(int s){
//默认对pair.first 的大小进行排序，greater<class>构成一个小顶堆
priority_queue<P,vector<P>,greater<P> > que;
//初始化距离
memset(d,INF,sizeof d);
d = 0;
que.push(P(0,s)); //把起点推入队列
while(!que.empty())
{
P p = que.top(); que.pop();
int v = p.second; //顶点的编号
if (d[v] < p.first) continue;//d[v]可能经过松弛后变小了，原压入堆中的路径失去价值
for(int i = 0; i < G[v].size(); i++){//利用最短边进行松弛
edge e = G[v];
if (d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
PS：
广告时间啦~
理工狗不想被人文素养拖后腿？不妨关注微信公众号：
|
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2023-3-28 07:11
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡