每日一练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算法求最短路径-创新互联
文章出自：http://cqcxhl.com/article/ddcgdh.html