迪杰斯特拉+DFS(应用)

69 阅读 0 评论 46 点赞

我是靠谱客的博主老迟到白昼，最近开发中收集的这篇文章主要介绍迪杰斯特拉+DFS(应用)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://blog.csdn.net/qq_37597345/article/details/82184587 这篇博客写得很好,题目的形式写的很全，推荐大家学习，在迪杰斯特拉一些应用上写的很好。我们可以从中学到很多的东西，就比如这个 PAT 当中有很多图论题目，大部分都是需要输出最短路径，还有求我们所走过的权值尽可能大，或者尽可能小，问题的形式有

1.新增边权

给定每一条边有一定的权值，要求在最短路径有多条时要求路径上的花费之和最小或者最大

具体我们应该在迪杰斯特拉函数当中增加一些操作，就是上面那个博客中所说的一样，这样我们就可以解决这类问题。

void di(int s)
{
fill(d,d+maxn,inf);
d[s]=0;
for(int i=0;i<n;i++)
{
int pos=-1,min =inf;
for(int j=0;j<n;j++)
{
if(!vis[j]&&d[j]<min)
{
pos=i;min=d[j];
}
}
if(pos=-1)
break;
vis[pos]=1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&d[j]>maap[pos][j]+d[pos])
{
d[j]=maap[pos][j]+d[pos];
ans[j]=ans[pos]+cost[pos][j];
}
else if(!vis[j]&&d[j]==maap[pos][j]+d[pos])
{
if(ans[j]>ans[pos]+cost[pos][j])
ans[j]=ans[pos]+cost[pos][j];
}
}
}
}

2.新增点权

给定每一个点的权值，要求在最短路径上要求点权最大，在函数中改变一些条件们可以解决问题。

void di(int s)
{
fill(d,d+maxn,inf);
d[s]=0;
for(int i=0;i<n;i++)
{
int pos=-1,min =inf;
for(int j=0;j<n;j++)
{
if(!vis[j]&&d[j]<min)
{
pos=i;min=d[j];
}
}
if(pos=-1)
break;
vis[pos]=1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&d[j]>maap[pos][j]+d[pos])
{
d[j]=maap[pos][j]+d[pos];
ans[j]=ans[pos]+val[j];
}
else if(!vis[j]&&d[j]==maap[pos][j]+d[pos])
{
if(ans[j]>ans[pos]+val[j])
ans[j]=ans[pos]+val[j];
}
}
}
}

3.直接询问有多少条最短路径

在一次团体程序设计天梯赛中遇到过一次，当时不知道怎么办。现在搞清楚了。

void di(int s)
{
fill(d,d+maxn,inf);
d[s]=0;
num[s]=1;
//起始点需要赋值为1
for(int i=0;i<n;i++)
{
int pos=-1,min =inf;
for(int j=0;j<n;j++)
{
if(!vis[j]&&d[j]<min)
{
pos=i;min=d[j];
}
}
if(pos=-1)
break;
vis[pos]=1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&d[j]>maap[pos][j]+d[pos])
{
d[j]=maap[pos][j]+d[pos];
num[pos]=num[j];
//这里是换了边
}
else if(!vis[j]&&d[j]==maap[pos][j]+d[pos])
num[j]+=num[pos];
}
}
}

以上的知识点可能会一起出现在一个题目中，我们也可以不写进函数里面去，而是写道函数外面去，我们也可以使用另一种方法来求出上面这些问题。如果我们都知道了，我们的最短路径（可能有很多条路），我们可以将每一条路都保存下来，我们就可以搜索出来一个符合要求的路径，达到题目的要求。

首先，我们需要做的就是先把最优的路径保存下来，我们来看这个，这个是在迪杰斯特拉函数里面的，我们用这个来找最短的路径的。

for(int j=0;j<n;j++)
{
if(!vis[j]&&d[j]>maap[pos][j]+d[pos])
//发现了更短的路径，我们需要先清空，然后再加入
{
d[j]=maap[pos][j]+d[pos];
pre[j].clear();
pre[j].push_back(pos);
}
else if(!vis[j]&&d[j]==maap[pos][j]+d[pos])	//这个是又来了一个路径，一样短的，我们直接加入进去
pre[j].push_back(pos);
}

1.增加了边权的一个图，我们DFS可以写为这样


#include<iostream>
using namespace std;
const int maxn=1005;
#include<bits/stdc++.h>
const int inf=0xfffffff;
vector<int>pre[maxn];
vector<int>path,temppath;
int cost[maxn][maxn];
int mincost=inf;
int s;
void dfs(int v)
{
temppath.push_back(v);
if(v==s)
{
int tempcost=0;
for(int i=temppath.size()-1;i>0;i--)
{
int id=temppath[i];
int next=temppath[i-1];
tempcost+=cost[id][next];
}
if(tempcost<mincost)
{
path=temppath;
mincost=tempcost;
}
temppath.pop_back();
return ;
}
for(int i=0;i<pre[v].size();i++)
dfs(pre[v][i]);
temppath.pop_back();
}
int main()
{
return 0;
}

2。还有增加点权的图：

void dfs(int v)
{
temppath.push_back(v);
if(v==s)
{
int tempval=0;
for(int i=temppath.size()-1;i>=0;i--)
{
int id=temppath[i];
tempval+=val[id];
}
if(temp<minval)
{
path=temppath;
minval=temp;
}
temppath.pop();
return ;
}
for(int i=0;i<pre[v].size();i++)
dfs(pre[v][i]);
temppath.pop_back();
}

3.计算路径的话，我们直接写在迪杰斯特拉函数里面就行，本身也没有多少代码，其实上面几个写法都可以直接写在迪杰斯特拉函数里面的。

受益颇多，总结了一下迪杰斯特拉的应用和用法。

PAT 上有一些题目，正好是这几个应用，可以去做一做题目，受益颇多。