当前位置:网站首页>2020.02.11
2020.02.11
2022-07-06 02:24:00 【weisir1】
I learned it today djs Algorithm , Let's summarize .
This algorithm is to find the shortest path of a single source . Now I'll give you the template and ideas , Be clear at a glance .
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f; // infinity , Not adjacent is infinite
int G[N][N], dis[N]; // G Is the adjacency matrix ,dis Single source to i A weight
int p[N]; // Record the precursor
bool book[N]; // Determine whether it has been added to the set , The set represents the updated nodes
int n;
void dijkstra(int u, int n) // u It's the source , The shortest path from the source point to each vertex ,n It's a fixed number
{
for (int i = 1; i <= N; i++) // initialization
{
dis[i] = G[u][i];
book[i] = 0;
/*
if (dis[i] == INF) // If it is equal to INF, Express u Can't reach this vertex , The precursor is -1
p[i] = -1;
else
p[i] = u;
*/
}
dis[u] = 0; // u To u A weight of 0
book[u] = 1; // Express u Updated
for (int i = 1; i < n; i++) // Find the smallest and update dis
{
// printf("=============\n");
int min = INF, t = u;
for (int j = 1; j <= n; j++)
if (!book[j] && dis[j] < min) // If j Not updated and adjacent
{
min = dis[j];
t = j;
}
if (t == u) // Optimize
return;
book[t] = 1;
// printf("t:%d\n", t);
for (int j = 1; j <= n; j++)
{
if (!book[j] && dis[j] > dis[t] + G[t][j]) // If a vertex is at the same time and u and t Adjacency , Update dis[j] Value
{
// printf("dis[j]:%d\n", dis[j]);
dis[j] = dis[t] + G[t][j];
// p[j] = t; // change j The precursor of t
// printf("dis[j]:%d\n", dis[j]);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
G[i][j] = INF;
cin >> n;
for (int i = 1; i <= n - 1; i++)
for (int j = i + 1; j <= n; j++)
cin >> G[i][j];
dijkstra(1, n);
cout << dis[3] << endl;
}
边栏推荐
- Computer graduation design PHP college student human resources job recruitment network
- Global and Chinese market of wheelchair climbing machines 2022-2028: Research Report on technology, participants, trends, market size and share
- Method of changing object properties
- 数据工程系列精讲(第四讲): Data-centric AI 之样本工程
- [postgraduate entrance examination English] prepare for 2023, learn list5 words
- Get the relevant information of ID card through PHP, get the zodiac, get the constellation, get the age, and get the gender
- 模板_求排列逆序对_基于归并排序
- How does redis implement multiple zones?
- MySQL (IV) - transactions
- How to check the lock information in gbase 8C database?
猜你喜欢
Executing two identical SQL statements in the same sqlsession will result in different total numbers
2022 eye health exhibition, vision rehabilitation exhibition, optometry equipment exhibition, eye care products exhibition, eye mask Exhibition
PAT甲级 1033 To Fill or Not to Fill
Social networking website for college students based on computer graduation design PHP
[postgraduate entrance examination English] prepare for 2023, learn list5 words
How does redis implement multiple zones?
【无标题】数据库中一条查询SQL执行的过程
论文笔记: 图神经网络 GAT
[Wu Enda machine learning] week5 programming assignment EX4 - neural network learning
安装php-zbarcode扩展时报错,不知道有没有哪位大神帮我解决一下呀 php 环境用的7.3
随机推荐
[robot hand eye calibration] eye in hand
Pangolin Library: subgraph
Method of changing object properties
Number conclusion LC skimming review - 1
Pat grade a 1033 to fill or not to fill
VIM usage guide
MySQL learning notes - subquery exercise
A basic lintcode MySQL database problem
模板_求排列逆序对_基于归并排序
Minecraft 1.16.5 生化8 模组 2.0版本 故事书+更多枪械
【无标题】数据库中一条查询SQL执行的过程
Prepare for the autumn face-to-face test questions
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
UE4 - how to make a simple TPS role (I) - create a basic role
[depth first search] Ji Suan Ke: Betsy's trip
2022 eye health exhibition, vision rehabilitation exhibition, optometry equipment exhibition, eye care products exhibition, eye mask Exhibition
我把驱动换成了5.1.35,但是还是一样的错误,我现在是能连成功,但是我每做一次sql操作都会报这个
SQL statement
How to generate rich text online
在线怎么生成富文本