THE_ALGORITHMS Telegram 4603
Алгоритм Флойда — Уоршелла

алгоритм динамического программирования, используемый для поиска кратчайших путей между всеми парами вершин во взвешенном ориентированном графе.

Алгоритм:
1. Создайте матрицу для хранения кратчайших расстояний между всеми парами вершин и инициализируйте ее.
2. Каждую вершину графа рассматривайте как промежуточную вершину пути.
3. Обновите матрицу, учитывая, приводит ли использование промежуточной вершины к более короткому пути между любой парой вершин.
- Для каждой пары вершин (i, j) рассмотрим все вершины (k) как потенциальные промежуточные звенья:
- Если путь от вершины i до j через вершину k короче текущего расстояния от i до j, обновите расстояние в матрице.
4. Продолжайте, пока не будут рассмотрены все пары вершин.

Сложность: O(V^3)



tgoop.com/the_algorithms/4603
Create:
Last Update:

Алгоритм Флойда — Уоршелла

алгоритм динамического программирования, используемый для поиска кратчайших путей между всеми парами вершин во взвешенном ориентированном графе.

Алгоритм:
1. Создайте матрицу для хранения кратчайших расстояний между всеми парами вершин и инициализируйте ее.
2. Каждую вершину графа рассматривайте как промежуточную вершину пути.
3. Обновите матрицу, учитывая, приводит ли использование промежуточной вершины к более короткому пути между любой парой вершин.
- Для каждой пары вершин (i, j) рассмотрим все вершины (k) как потенциальные промежуточные звенья:
- Если путь от вершины i до j через вершину k короче текущего расстояния от i до j, обновите расстояние в матрице.
4. Продолжайте, пока не будут рассмотрены все пары вершин.

Сложность: O(V^3)

BY Алгоритмы и структуры данных




Share with your friend now:
tgoop.com/the_algorithms/4603

View MORE
Open in Telegram


Telegram News

Date: |

In handing down the sentence yesterday, deputy judge Peter Hui Shiu-keung of the district court said that even if Ng did not post the messages, he cannot shirk responsibility as the owner and administrator of such a big group for allowing these messages that incite illegal behaviors to exist. To delete a channel with over 1,000 subscribers, you need to contact user support Each account can create up to 10 public channels Telegram message that reads: "Bear Market Screaming Therapy Group. You are only allowed to send screaming voice notes. Everything else = BAN. Text pics, videos, stickers, gif = BAN. Anything other than screaming = BAN. You think you are smart = BAN. Telegram channels enable users to broadcast messages to multiple users simultaneously. Like on social media, users need to subscribe to your channel to get access to your content published by one or more administrators.
from us


Telegram Алгоритмы и структуры данных
FROM American