Dijkstra算法是一种用于图论问题中求解最短路径的经典算法。该算法的主要思想是从起始点开始，将所有点分为两个集合，一个集合是已经求得最短路径的点的集合，另一个集合是未求得最短路径的点的集合。每次从未求得最短路径的点中选择距离起始点最近的点加入已求得最短路径的点的集合中，并且更新与该点相邻的点到起点的距离。重复这个过程直到所有点都加入到已求得最短路径的点的集合中，最终得到起始点到其他节点的最短路径。

下面是Dijkstra算法的C++模板：

const int INF = 0x3f3f3f3f;
struct Edge
  int to;
  int cost;
;
vector<Edge> G[MAXN];
int dist[MAXN];
bool vis[MAXN];
void dijkstra(int s, int n) {
  memset(vis, false, sizeof(vis));
  memset(dist, INF, sizeof(dist));
  dist[s] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
  que.push(make_pair(0, s));
  while (!que.empty()) {
    pair<int, int> p = que.top();
    que.pop();
    int v = p.second;
    if (vis[v]) continue;
    vis[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
      Edge e = G[v][i];
      if (dist[e.to] > dist[v] + e.cost) {
        dist[e.to] = dist[v] + e.cost;
        que.push(make_pair(dist[e.to], e.to));
      }
    }
  }
}

该模板使用了一个结构体Edge来存储边信息，其中to表示终点，cost表示边权值。G数组用于存储图的信息，其下标表示该点的编号，对应的存储的是从该点出发的边的信息。dist数组存储从起始点到每个节点的最短距离，vis数组表示该点是否已经加入已求得最短路径的点的集合中。

该模板中除了常数INF用于初始化dist数组外，其余的值都可以根据实际情况进行调整和修改。

总的来说，Dijkstra算法是一种十分经典的算法，应用广泛。通过本篇文章的C++模板，我们可以更好地理解该算法的实现过程和细节，进而将其运用到实际场景中去。

相似文章
• C++中的ceil函数是什么意思？
  C++是一门广泛使用的编程语言，用于开发各种类型的软件应用程序。在C++编程中，有许多内置函数可供开发人员使用，其中一个常见的函数是ceil函数。
  
  
• C++编写爱心形图案
  C++编程语言是一种高级编程语言，被广泛地用于编写各种类型的软件程序。如今，很多人学习编程语言，一般来说，他们会首先学习一些基本的代码语法。然而，有些人会试着尝试一些有趣的项目，例如编写代码控制计算机打印出爱心形图案。
  
  
• C++强制类型转换String
  C++是一种面向对象的编程语言，广泛用于开发各种应用程序和系统软件。C++中的强制类型转换是一种将一种类型的数据转换为另一种类型的数据的技术。在一些情况下，开发人员需要将数据从一种类型转换为另一种类型，以便能够进行更高效或更明确的操作。本文
  
  
• C++标准化：重要性及未来发展趋势
  C++是一种通用编程语言，常用于开发操作系统、大数据处理和游戏等复杂应用程序。它的主要优点包括高效性和灵活性，但也会带来许多挑战。因此，C++标准化的重要性越来越受到重视。
  
  
• 如何在C++中给string类型赋值？
  在C++编程中，string类型是非常常用的数据类型，它可用于存储字符串。如果你是初学者，可能不太清楚如何给string类型赋值。在本文中，我们将介绍如何赋值string变量，以帮助你更好地理解和使用这种数据类型。
  
  
• "VC++ 2019: 最新版本的C++编程工具"
  VC++
  
  
• C++编程规范PDF下载
  C++是一种广泛使用的编程语言，有很多人喜欢使用它来进行软件开发和编程。但是，如果不遵循适当的编程规范，将会给项目带来许多问题和麻烦，同时也会影响团队开发的效率。因此，我们需要在编写代码时遵循一些C++编程规范。
  
  
• C++编写矩形类的定义
  矩形是一种常见的二维图形，具有面积和周长等特征。在计算机编程中，矩形的定义和使用非常普遍。C++语言提供了支持矩形类的定义，可以方便地创建和操作矩形对象。
  
  
• Dev C++无法运行问题解决方案
  在使用Dev
  
  
• C++是否适合开发API接口？
  C++是一种高效且强大的编程语言，经常被用于开发系统级应用程序和高性能游戏等。但是，它是否适合用于开发API接口呢？
  
  
• C++编写加法程序
  C++是一种非常流行的编程语言，它具有高效、灵活和难度适中的特点。在C++中，我们可以非常简单地编写一个加法程序，来进行两个数的相加运算。
  
  
• C++ 求解素数个数之间的两个数。
  C++
  
  
• C++内存地址冲突问题：大小端转换解决方案
  C++是一种强类型语言，能够有效地帮助开发者实现各种复杂的操作。然而，C++中存在一个非常棘手的问题，那就是内存地址冲突。
  
  
• Modern C++语言核心特性解析电子版
  Modern
  
  
• C++在Mac上可否运行？
  C++是一种广泛使用的编程语言，能够通过编写代码实现许多应用程序和软件。而Mac是一款出色的电脑，其操作系统是基于UNIX的，很多开发者都想知道C++是否能在Mac上运行。本文将针对这一问题进行详细的探讨。
  
  
• 如何在C++中更改字体大小？
  在C++中更改字体大小是一项非常常见的任务，通常是因为开发人员需要在GUI应用程序中显示不同大小的文本。有几种方法可以在C++中更改字体大小，本文将向您介绍其中的两种。
  
  
• C++中如何表示幂？
  在C++中，幂可以使用特定的函数或简单的运算符来表示。以下是C++中表示幂的两种常见方法：
  
  
• C++面向过程编程原理与实践
  C++是一种流行的编程语言，不仅支持面向对象编程，还支持面向过程编程。在面向过程编程中，程序被分解为一系列函数，每个函数都执行特定的任务。本文将介绍C++面向过程编程的原理和实践。
  
  
• C++中如何表示分数
  在C++中，分数可以通过两个整数来表示，这两个整数分别表示分子和分母。分子是分数的上部，表示被分数的等分中有几份；而分母是下部，表示被分数的等分被分成了几份。在C++中，我们通常使用一个类来表示分数，这个类可以包括以下几个部分：
  
  
• C++迭代器的使用方法
  C++是一种非常流行的编程语言，在编程中，它有许多功能和工具能够帮助程序员更好地管理和处理数据。其中，迭代器是一个非常重要的工具，它可以让程序员通过简单的方法来迭代容器中的元素。
  
  
• C++如何获取鼠标点击坐标？
  C++是一种广泛使用的编程语言，它可以用于开发各种类型的应用程序、操作系统和游戏等。在许多情况下，我们需要获取用户的鼠标点击坐标来执行某些操作。在本文中，我们将展示如何在C++中获取鼠标点击坐标。
  
  
• C++字符数组：输出十个名字
  C++字符数组是一种非常常见的数据类型，它可以用来存储一组字符数据。在实际编程中，我们常常需要用字符数组来存储一些字符串，比如姓名、地址、电话等等。在本篇文章中，我们将用C++字符数组来输出十个名字。
  
  
• 如何在C++6.0中运行代码？
  C++6.0是一种编程语言，它的编译器可以在多种操作系统上使用。下面是在Windows环境下使用C++6.0编译器运行代码的步骤：
  
  
• "C++标准模板库PDF下载"
  C++标准模板库（STL）是C++编程语言中的一个标准库，旨在为程序员提供一组通用的数据结构和算法。STL的主要特点是它是一种模板技术，可以适用于各种数据类型。其中包括容器，如向量，列表，映射等，以及算法，如排序，搜索等。
  
  
• 学习C++前是否需要学习Python？
  对于初学者来说，学习C++前是否需要学习Python这个问题，其实并没有一个确定的答案。因为这主要取决于你的学习目的以及对编程的了解程度。
  
  
• 如何在C++循环中设定初始值
  在C++编程中，循环是最基本的控制结构之一。循环语句可以帮助我们重复执行一段代码，这在许多情况下非常有用。然而，在设置循环时，很重要的一点是为循环变量设定一个合适的初始值。在本文中，我们将探讨如何在C++循环中设置初始值。
  
  
• C++中使用自定义sort函数排序
  在C++中，sort函数是一个非常常用的函数，用于对数组或容器中的元素进行排序。然而，在某些情况下，我们可能需要对特定的数据类型进行排序，并且需要一些自定义的规则来进行排序。这时候，我们可以使用自定义sort函数来实现。
  
  
• 如何判断Microsoft Visual C++错误信息
  Microsoft
  
  
• C++向量的元素交换操作
  在C++语言中，向量（vector）是一种特殊的数据结构，它可以动态地调整大小，比数组更加灵活。而在向量的操作中，元素交换操作是非常常见的，可以用于排序、查找和其他一些算法中。
  
  
• C和C++是否为两种不同的编程语言？
  C语言和C++都是被广泛使用的编程语言，但是很多人都在争论它们是否是两种不同的编程语言。实际上，这个问题并不是那么容易回答。
  
  
• C++随机生成1至100的数字
  在计算机编程中，随机数生成是非常常见的操作。而在C++编程中，我们可以利用rand()函数来生成随机数。下面，我们就来介绍如何在C++中生成1至100之间的随机数。
  
  
• C++模块化编程：简化代码，提高效率
  随着软件开发周期的缩短和需求变化的不断出现，模块化编程变得越来越重要。C++语言的模块化编程功能允许开发人员将程序划分为更小的、相互独立的部分，这些部分可以在不同的文件中编写，然后按需组合使用，这使得开发人员能够更有效地管理和维护代码。本文
  
  
• 详解C++贪吃蛇代码
  贪吃蛇是一款经典的游戏，很多人会尝试使用C++来编写贪吃蛇代码来锻炼自己的编程能力。下面我们来详细解析一下C++贪吃蛇代码。
  
  
• C++双端队列的声明中出现内存重复分配问题
  C++是一门广泛使用的编程语言，它广泛应用于各种类型的软件开发中，从游戏和图形应用程序到操作系统和网络驱动程序。在C++中，双端队列是一种常用的数据结构，其允许在队列的两端插入或删除元素。
  
  
• 如何在C++中重复执行while语句？
  在C++中，使用while循环语句可以重复执行特定的代码块，只要循环条件为真。这种循环非常适合需要重复处理一些任务直到满足某种条件的情况。
  
  
• 如何在Dev C++中创建新项目
  Dev
  
  
• C++通讯录课程设计
  在计算机科学领域中，通讯录程序的实现一直是一项非常常见的任务，它可以帮助人们方便地管理自己的联系人。在C++语言中，实现一个通讯录程序同样很容易，需要掌握的知识点包括定义结构体、使用文件读写，以及图形化界面设计等方面。
  
  
• C++ 调用 Python3 导致内存泄露问题
  在软件开发中，不同的编程语言常常需要进行互相调用。其中，C++
  
  
• 「C++类和对象二实验心得」
  在学习过程中，我发现通过实验来掌握概念会更容易。C++类和对象的实验是一种比较有效的学习方式。在这次实验中，我学习到了C++中类和对象的重要概念，并且学会了如何使用类和对象来编写程序。
  
  
• C++使用for循环判断斐波那契数列第n项被3整除，第一项为零。
  在计算机编程中，斐波那契数列是一个非常常见的数列，它的定义是每一项等于其前两项之和，即f(n)
  
  
• C++随机生成1到200之间的整数
  C++是一种面向对象的编程语言，它被广泛应用于软件开发、游戏开发、操作系统等各个领域。其中，随机数的生成在很多场景下都是必不可少的操作，比如游戏中的随机事件、密码的生成等等。本篇文章将介绍如何使用C++生成1到200之间的整数随机数。
  
  
• C++ 里的小于号 ( < )
  在C++中，小于号是一个重要的运算符，通常表示比较两个值的大小。小于号（<）只有一个功能：比较两个值，如果左边的值小于右边的值，则返回true，否则返回false。
  
  
• C语言如何实现C++对象？
  C++是C语言的扩展，它引入了面向对象编程的概念。但是有时候我们也需要在C语言中实现面向对象编程的功能。那么，在C语言中如何实现C++对象呢？
  
  
• 如何在Visual C++ 2010中显示行号
  Visual
  
  
• C++Word页码代码——实现文章自动编号
  随着现代科技的快速发展，使用电脑来撰写文章已经成为了广大人们不可或缺的工具。但是，想必同样使用Word来写作的你一定会遇到这样的问题：如何实现文章自动编号？
  
  
• C++环形缓冲区
  C++环形缓冲区是一种非常有用的数据结构，它可以有效地管理数据的读写，并且可以减少在系统中的一些数据拷贝操作。环形缓冲区实际上就是内存中一段指定大小的区域，我们可以把这个区域看成是一个环形的数组，实现一些特殊的功能。这篇文章将讲述C++环形
  
  
• C++程序设计的注意事项
  C++程序设计是一项重要的技能，而这项技能的掌握并不容易。在学习C++程序设计的过程中，需要注意一些事项，这些注意事项可以帮助您更好地学习和使用C++编程语言。以下是一些注意事项，供参考。
  
  
• 如何使用C++编写小游戏？
  C++是一种经典的编程语言，可以用于编写各类应用程序，其中一个常见的应用就是编写小游戏。如何使用C++编写小游戏呢？以下是一些指导性的步骤：
  
  
• 使用C++编写程序时的头文件——bits/stdc++.h
  在C++编程语言中，头文件是一种重要的文件，它可以让程序员在编写代码时使用预定义的函数和变量。在C++的头文件中，有一种非常有用且常用的头文件叫做“bits/stdc++.h”。
  
  
• C++实现RGB颜色生成，避免重复色彩
  对于一款色彩丰富的软件来说，RGB
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政