最短路径
Dijkstra
// 所有可到达顶点v都必须要未被访问 而且两者之间存在通路 这是一个大前提
for(int j = 0;j<n;j++)
{
if(vis[v]==0 && mp[u][j] != 0 && dist[j] > dist[u]+mp[u][j])
{
dist[j] = dist[u] + mp[u][j];
//源点到j的最短 更新成源点到u的最短距离 加上u到j的路径长度
}
}
朴素邻接矩阵做法
/*
解决单源无负权最短路问题
对图G(V,E)设置集合S,存放已经访问的结点
然后每次从集合V-S中选择与起点s的最短距离最小的结点u
访问并加入S
之后令u为中介点 优化起点s与所有可以通过u到达的v之间的距离
执行n次 直到可以包含所有顶点
主要的时间花在了外层循环n次 必须标记每个顶点以访问 无法优化
内层寻找最小的d[u]和优化最短距离 寻找最小的d[u]可以使用优先队列
为O(n*(n+n))
如果使用优先队列加上邻接表 时间复杂度可以实现O(VlogV + E)
*/
void Dij(int root){
dist[root] = 0;//自身到自身为0
for(int i = 0;i<n;i++)
{
//每次循环在里面找到最小的一个u
int u = -1;
int mx = inf;
for(int j = 0;j<maxn;j++)
{
// 这里需要判断这个结点是否访问过呢 肯定需要 不然一直选择起点
if(mx > dist[j] && vis[j]==0)
{
mx = dist[j];
u = j;
}
}
if(u == -1) return;//找不到最小 结束
vis[u] = 1;//代表已经访问
//需要更新dist的值 以u为中介看看是否可以更新距离
// 实际上这里就是遍历u的邻居结点 这里是可以优化性能的地方 也可以进行二次比较
for(int j = 0;j<n;j++)
{
if(vis[v]==0 && mp[u][j] != 0 && dist[j] > dist[u]+mp[u][j])
{
dist[j] = dist[u] + mp[u][j];
//源点到j的最短 更新成源点到u的最短距离 加上u到j的路径长度
}
}
}
}
实现路径打印
int pre[maxn];
/*
pre[v]表示从源点s到v的最短路径上v的前一个顶点 即前驱的编号
每次优化d[v]变得更小的方案是让u作为从s到v的最短路径前一个结点
*/
void Dij(int root){
dist[root] = 0;//自身到自身为0
for(int i = 0;i<n;i++)
{
//每次循环在里面找到最小的一个u
int u = -1;
int mx = inf;
for(int j = 0;j<maxn;j++)
{
// 这里需要判断这个结点是否访问过呢 肯定需要 不然一直选择起点
if(mx > dist[j] && vis[j]==0)
{
mx = dist[j];
u = j;
}
}
if(u == -1) return;//找不到最小 结束
vis[u] = 1;//代表已经访问
//需要更新dist的值 以u为中介看看是否可以更新距离
// 实际上这里就是遍历u的邻居结点
for(int v = 0;v<n;v++)
{
if(mp[u][v] != 0 && dist[v] > dist[u]+mp[u][v])
{
dist[v] = dist[u] + mp[u][v];
//源点到v的最短 更新成源点到u的最短距离 加上u到v的路径长度
pre[v] = u;// 到达v的最短路径前一个为u
}
}
}
}
/*
打印从s到v的路径 利用递归来寻找
pre[v]代表的是v的前驱结点
这个结构很有意思 因为对于图而言 具有一个子问题性质
就是假如a~b~c中a~c是最短路 则a~b也是最短路
因此实际上有很多最短路径都是在树的同一分支上 因此每次只需要从底层结点向上追溯即可
按道理来说 一个for循环也可以解决
*/
void printRoad(int s,int v)
{
if(s==v) {
cout << s <<" ";
return;
}
printRoad(s,pre[v]);
cout << v <<" ";
}
新增边权
/*
常见的操作还有三种 增加第二标准 进行排序选择
1. 给每个边在增加一个边权(比如花费)要求最短路径的基础上 花费最少
2.给每个点增加点权 最短路有多条的时候要求点权最大
3.最短路的路径条数
三种问题都只需要增加一个新的数组来存放新增的边权或点权或最短路径条数
然后只需要在Dij中修改优化d[v]的步骤即可
*/
int cost[maxn][maxn],c[maxn];// 某条边的第二权重 到达某点的总花费
/*
cost[u][v]代表u->v的边权花费
c[u]代表从起点s到顶点u的最小花费
初始化只有c[s]为0 其余皆为inf
*/
for(int v = 0;v<n;v++)
{
if(mp[u][v] != 0 && vis[v]==0){
if(&& dist[v] > dist[u]+mp[u][v]){
dist[v] = dist[u] + mp[u][v];
c[v] = c[u] + cost[u][v];
}else if(dist[v] == dist[u] + mp[u][v] && c[u] + cost[u][v] < c[v]){
// 满足上述条件 才进行c的更新
c[v] = c[u] + cost[u][v];
}
}
}
新增点权
/*
新增点权
用weight[u]代表结点u具有的点权
数组w[u]代表从起点到u可以收集最大的点权数
初始只有w[u]为weight[s] 其余皆为0
*/
int weight[maxn],w[maxn];
for(int v = 0;v<n;v++)
{
if(mp[u][v] != 0 && vis[v]==0){
if(dist[v] > dist[u]+mp[u][v]){
dist[v] = dist[u] + mp[u][v];
w[v] = w[u] + weight[v];// 到达了v 因此加上v的权值
}else if(dist[v] == dist[u] + mp[u][v] && w[u] + weight[v] > w[v]){
w[v] = w[u] + weight[v];
}
}
}
求最短路径条数
/*
求最短路径的条数
增加数组num[u] 从起点到u的最短路径条数
初始化num[s] = 1 其余都为0
当是不等关系 即dist[v] > dist[u]+mp[u][v] 更新num[v]的值
因为这个判断相当于 找到了更短的一个路径 所以理应里面的数据都变化
当dist[v] = dist[u]+mp[u][v] 意味着该中转是第二个最小路
num[v] += num[u] 在已有的基础不变的情况下 加入到达v的路径数
这个思路也能很好体现最优结构思想 只有在之前的状态都更新好了
再运用这些内容的时候 才不会影响后续运算
*/
int num[maxn];
for(int v = 0;v<n;v++)
{
if(mp[u][v] != 0 && vis[v]==0){
if(dist[v] > dist[u]+mp[u][v]){
dist[v] = dist[u] + mp[u][v];
num [v] = num[u]; //继承上一个结点的最短路径个数
}else if(dist[v] == dist[u] + mp[u][v]){//同为最短路 原有基础上叠加次数
num[v] += num[u];
}
}
}
尽管有上述的更新操作,但是其中是存在局限性的,假如求解的内容不满足最优子结构,就不可以使用上述修改思路,因此可以使用Dij+DFS
Dij+DFS
/*基本思路为 先在Dij算法中记录下所有最短路径 只考虑距离 然后再这些所有的路径中选择出一个第二尺标最优的路径
主要作用在于当不满足子结构的前提或者标尺的数量过多 容易写混
需要注意的是里面的vector<int> pre[maxn];对于这个pre数组的递归
会形成一棵递归树 而遍历这棵递归树的方法就是DFS
*/
for(int v = 0;v<n;v++)
{
if(mp[u][v] != 0 && vis[v]==0){
if(dist[v] > dist[u]+mp[u][v])
{
dist[v] = dist[u] + mp[u][v];
//源点到v的最短 更新成源点到u的最短距离 加上u到v的路径长度
pre[v].clear();// 每次更新最短路都需要重置数组
pre[v].push_back(u);// 到达v的最短路径前一个为u
}else if(dist[v] == dist[u]+mp[u][v]){
pre[v].push_back(u);//相等条件 添加路径
}
}
}
// 根据形成的pre数组 打印出所有路径 递归打印
int optValue;//第二尺度
int st = 0;// 路径起点 也是叶子节点
vector <int> path,temp;//最优路线和临时路线
void printRoad(int v) //v为当前访问结点
{
if(v==st){//递归边界 达到叶子结点
temp.push_back(st);
// 这里存在一系列的比较和赋值 根据最终的比较来
for(auto i : temp){
cout << i <<" ";
}
temp.pop_back();
return;
}
temp.push_back(v);
for(int i = 0 ;i < pre[v].size();i++){
printRoad(pre[v][i]); //递归其前驱节点
}
temp.pop_back();
}
Bell-Ford
/*
代码比较好写 但是思路并不是很简单
因为每层遍历实际上就会形成一层到达的结点 然后每次遍历一层结点都会进行松弛
(好牵强hhh)
*/
bool Ford(int s)// 表示源点
{
fill(d,d+n,inf);
d[s] = 0;//自身到自身的距离为0
for(int i = 0;i<n-1;i++) //执行n-1轮
{
for(int u = 0;u<n;u++)// 每轮遍历所有边(根据点来找所有边)
{
//找u的邻居
Node *p = head[u];
while(p!=NULL){
int v = p->id;
int dis = p->val;
if(d[u] + dis < d[v]){ //以u作为中介到达v的距离更小
d[v] = dis + d[u]; // 松弛操作
}
p = p->next;
}
}
}
for(int u = 0;u<n;u++)// 每轮遍历所有边(根据点来找所有边)
{
//找u的邻居
Node *p = head[u];
while(p!=NULL){
int v = p->id;
int dis = p->val;
if(d[u] + dis < d[v]){ //以u作为中介到达v的距离更小
return false;// 如果还能松弛 说明存在负闭环
}
p = p->next;
}
}
return true;
}
