无向图的最短路径—-迪杰斯特拉算法—-(包括:花费问题,物资问题,条数问题)

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

迪杰斯特拉算法如果不熟悉的话从这里开始看。。。。如果已经明白了迪杰斯特拉算法而想知道花费问题、城市之间的物资问题、最短路径条数问题的朋友可以往下翻。。。。

一、迪杰斯特拉算法讲解

算法思想是从起点开始,找到一条起点能到达顶点中的边权最小的那个点,然后从这个点开始更新起点和该点共有的点的最短路径。。思想看起来很好懂,实际编码实现还是有难度的。

我说一个我的思路:

1、初始时把图(不管是有向图还是无向图) 中的各个边的权重设置为无穷大。 从起点到各个点的距离设置为无穷大。 每个点是否经过的标记设置为false。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;         
const int maxv = 1000;      ///最大顶点数
int G[maxv][maxv];          ///图
int n,m,s;      ///n表示顶点数,m表示变数,s为起点
int d[maxv];        ///从起点到各个点的距离
bool vis[maxn] = {false};
int main()
{
    
    return 0;
}

注意:maxn 表示最大数的时候,0x表示16进制,要用0x3fffffff而不是用0x7ffffff;

2、从p键盘接受各个点之间的路径

int main()
{
    int u,v,w;
    scanf("%d%d%d",&n,&m,&s);
    fill(G[0],G[0]+maxv*maxv,INF);          ///将图初始化的一种方式  慎用memset
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        G[u][v] = w;
        G[v][u] = w;        ///无向图加上这句话
    }
    
    return 0;
}

3.开始写迪杰斯特拉算法

1): 将从起点各个点的路径的距离设置为最大,并将起点到自身的距离设置为0;

void Dijkstra(int s)
{
    fill(d,d+maxv,INF);
    d[s] = 0;
}

2): 因为有n个顶点,所以开始n次循环

首先我们设置两个变量,u(是d[u]最小)和minnum(存放最小的d[u])。

然后找到图中未访问的结点中d[j]的最小值。

分支情况:如果找不到,则说明剩下的点和s不连通,返回;

如果找到:标记u点为访问过; 开始再次访问图中的结点(记为V )

如果该结点未被访问并且u能到该点并且以u为中介点可以让d[v]更小,则更新

void Dijkstra(int s)
{
    fill(d,d+maxv,INF);
    d[s] = 0;
    for(int i=0; i<n; i++)  ///整体的循环
    {
        int u = -1,minnum = INF;
        for(int j=0; j<n; j++)
            {
                if(vis[j] == false && d[j] < minnum)
                {
                    u = j;
                    minnum = d[j];
                }
            }
        if(u == -1 )    return ;            ///如果找不到
        vis[u] = true;
        for(int v=0; v<n; v++)
        {
            if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] +G[u][v];       ///优化最短路
            }
        }
    }
}

所以连起来就是:

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;         
const int maxv = 1000;      ///最大顶点数
int G[maxv][maxv];          ///图
int n,m,s;      ///n表示顶点数,m表示变数,s为起点
int d[maxv];        ///从起点到各个点的距离
bool vis[maxn] = {false};
void Dijkstra(int s)
{
    fill(d,d+maxv,INF);
    d[s] = 0;
    for(int i=0; i<n; i++)  ///整体的循环
    {
        int u = -1,minnum = INF;
        for(int j=0; j<n; j++)
            {
                if(vis[j] == false && d[j] < minnum)
                {
                    u = j;
                    minnum = d[j];
                }
            }
        if(u == -1 )    return ;            ///如果找不到
        vis[u] = true;
        for(int v=0; v<n; v++)
        {
            if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] +G[u][v];       ///优化最短路
            }
        }
    }
}
int main()
{
    int u,v,w;
    scanf("%d%d%d",&n,&m,&s);
    fill(G[0],G[0]+maxv*maxv,INF);          ///将图初始化的一种方式  慎用memset
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        G[u][v] = w;
        G[v][u] = w;        ///无向图加上这句话
    }
    Dijkstra(s);        ///迪杰斯特拉算法入口
    for(int i=0; i<n; i++)
        printf("%d ",d[i]);
    return 0;
}

二、我们来看看提到的花费啊,物资啊等问题

既然懂了迪杰斯特拉算法,那么题目肯定不会考的这么“裸”,最常见的三种问题就是:

1:给每条再增加一个边权(比如说花费),然后求在最短的路径有多条时要求路径上的花费最小(也可以是别的含义,求最大)

2:给每个点增加一个点权(比如从每个城市能收集到的物资),然后在最短路径有多条的时候要求路径上的点权之和最大(同理,也可以是最小)

3:直接问有多少最短路径

我们来看看解法

针对一增加边权,那我们在增加一个数组cost[u][v] ,表示从u到v的花费,在增加一个数组c[],作用跟d[]一样,初始化时也设置为INF,起点s设置为0。在优化边的代码中更改如下:

 for(int v=0; v<n; v++)
        {
            if(vis[v] == false && G[u][v] != INF)
            {
                if(d[u] + G[u][v] < d[v])      ///优化最短路
                {
                    d[v] = d[u] +G[u][v];
                    c[v] = c[u] + cost[u][v];
                }else if(d[u] +G[u][v] == d[v] && c[u] + cost[u][v] < c[v])
                {
                    c[v] = c[u] + cost[u][v];
                }
            }
        }

 

针对二,增加点权问题,我们加一个数组weight[u]表示城市u中的物资数目,(由题中给出),并增加一个数组w[],令从起点s到顶点u可以收集到的物资为w[u] .

 for(int v=0; v<n; v++)
        {
            if(vis[v] == false && G[u][v] != INF)
            {
                if(d[u] + G[u][v] < d[v])      ///优化最短路
                {
                    d[v] = d[u] +G[u][v];
                    w[v] = w[u] + weight[v];
                }else if(d[u] +G[u][v] == d[v] && w[u] + weight[v] > w[v])
                {
                    w[v] = w[u] + weight[v];
                }
            }
        }

针对三,只需要增加一个数组num[],令其从起点s到u的最短路径为num[u] , 初始化时只有num[s] = 1 其余为0,

 for(int v=0; v<n; v++)
        {
            if(vis[v] == false && G[u][v] != INF)
            {
                if(d[u] + G[u][v] < d[v])      ///优化最短路
                {
                    d[v] = d[u] +G[u][v];
                    num[v] = num[u];
                }else if(d[u] +G[u][v] == d[v])
                {
                    num[v] += num[u];
                }
            }
        }

基本上迪杰斯特拉考的问题就这些。注意只是正边权问题!!

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《无向图的最短路径—-迪杰斯特拉算法—-(包括:花费问题,物资问题,条数问题)》 发布于2018-07-22

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录