每日一练c++题目日刊|第九期:Dijkstra算法求最短路径-创新互联

文章目录
  • 第一题:Dijkstra 算法求最短路径
    • 题目描述
    • 输入格式
    • 输出格式
    • 输入样例
    • 输出样例
    • 解题思路&C++题解

目前创新互联建站已为上千家的企业提供了网站建设、域名、网站空间、网站托管、服务器托管、企业网站设计、呼兰网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。第一题:Dijkstra 算法求最短路径 题目描述

给定一个有向图 G = ( V , E ) G=(V,E) G=(V,E),其中 V V V 为节点集合, E E E 为边集合。每条边 ( u , v ) (u,v) (u,v) 有一个权值 w ( u , v ) w(u,v) w(u,v),表示从节点 u u u 到节点 v v v 的边权。请你编写一个程序,计算出从节点 s s s 到节点 t t t 的最短路径。

输入格式

第一行包含三个整数 n , m , s n,m,s n,m,s,分别表示节点数、边数和起始节点。

接下来 m m m 行,每行包含三个整数 u , v , w u,v,w u,v,w,表示一条边 ( u , v ) (u,v) (u,v) 的起点、终点和边权。

最后一行包含一个整数 t t t,表示终点。

输出格式

如果存在从节点 s s s 到节点 t t t 的路径,则输出最短路径的长度。否则输出 − 1 -1 −1。

约定:路径的长度为路径上所有边的权值之和。

输入样例
5 8 0
0 1 1
0 2 12
1 2 9
1 3 3
2 3 5
2 4 5
3 2 4
3 4 13
4
输出样例
8
解题思路&C++题解

此题可以使用 Dijkstra 算法来解决,Dijkstra 算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2),因此此题的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

Dijkstra 算法流程如下:

  1. 初始化距离数组dis,将距离数组的所有元素赋值为无穷大,将起点的距离赋值为0。

  2. 初始化一个未访问集合 v i s vis vis,表示所有节点是否已经被访问过。

  3. 将起点加入未访问集合 v i s vis vis。

  4. 对于起点的每一个邻居节点 v v v,更新距离数组 d i s dis dis: d i s [ v ] = min ⁡ ( d i s [ v ] , d i s [ u ] + w ( u , v ) ) dis[v]=\min(dis[v],dis[u]+w(u,v)) dis[v]=min(dis[v],dis[u]+w(u,v))。

  5. 从未访问集合 v i s vis vis 中选择一个距离最小的节点 u u u,将其加入已访问集合中。

  6. 对于节点 u u u 的每一个邻居节点 v v v,更新距离数组 d i s dis dis: d i s [ v ] = min ⁡ ( d i s [ v ] , d i s [ u ] + w ( u , v ) ) dis[v]=\min(dis[v],dis[u]+w(u,v)) dis[v]=min(dis[v],dis[u]+w(u,v))

  7. 重复步骤 5 和 6 直到未访问集合为空。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

空间复杂度: O ( n 2 ) O(n^2) O(n2)

下面是 c++ 代码实现:

#include#include#include 

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m, s;
int g[N][N]; // 邻接矩阵
int dis[N];  // dis[i] 表示从起点到 i 的最短路径长度
bool vis[N]; // vis[i] 表示节点 i 是否已经被访问过

// Dijkstra 算法
void dijkstra()
{// 初始化距离数组和未访问集合
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    dis[s] = 0;

    // 循环直到未访问集合为空
    while (true)
    {// 从未访问集合中选择一个距离最小的节点 u
        int u = -1, min_dis = INF;
        for (int i = 0; i< n; i++)
            if (!vis[i] && dis[i]< min_dis)
            {u = i;
                min_dis = dis[i];
            }

        // 如果未访问集合为空,则退出循环
        if (u == -1)
            break;

        // 将节点 u 加入已访问集合
        vis[u] = true;

        // 更新节点 u 的所有邻居节点的距离
        for (int v = 0; v< n; v++)
            if (g[u][v] != INF)
                dis[v] = min(dis[v], dis[u] + g[u][v]);
    }
}

int main()
{cin >>n >>m >>s;

    // 初始化邻接矩阵
    memset(g, 0x3f, sizeof g);
    while (m--)
    {int u, v, w;
        cin >>u >>v >>w;
        g[u][v] = w;
    }

    int t;
    cin >>t;

    // 调用 Dijkstra 算法
    dijkstra();

    // 输出从起点到终点的最短路径长度
	if (dis[t] != INF)
		cout<< dis[t]<< endl;
	else
		cout<< -1<< endl;
	
	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享题目:每日一练c++题目日刊|第九期:Dijkstra算法求最短路径-创新互联
文章URL:http://myzitong.com/article/ddcgdh.html