Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа

@t0lyan · Регистрация: 08.05.2015

Студворк — интернет-сервис помощи студентам

Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа. Указать кратчайший маршрут из вершины v1 в вершину v4.

@t0lyan · 02.07.2016, 20:12 **[ТС]**

По поводу коротких путей:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{\nu }_{1} \ \rightarrow {\nu }{2} \equiv {e}_{1} \\{\nu }_{1} \ \rightarrow {\nu }{3} \equiv {e}_{10} \\{\nu }_{1} \ \rightarrow {\nu }{4} \equiv {e}_{6}, {e}_{9} \\{\nu }_{1} \ \rightarrow {\nu }{5} \equiv {e}_{6}, {e}_{5} \\{\nu }_{1} \ \rightarrow {\nu }{6} \equiv {e}_{6} \\$

Кратчайший путь из v1 в v4, будет через направления е6 и е9...

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{\nu }_{1} \ \rightarrow {\nu }{4} \equiv {e}_{6}, {e}_{9}$

@3D Homer · 02.07.2016, 20:39

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

Про кратчайший путь из v1 в v4 я согласен, но путь v1, v6, v5, v4 имеет ту же длину.

@t0lyan · 03.07.2016, 10:41 **[ТС]**

Тогда так?
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{\nu }_{1}\rightarrow {\nu }{2}\ =\ {e}_{1}\ =\ 3\\{\nu }_{1}\rightarrow {\nu }{3}\ =\ {e}_{10}\ =\ 2\\{\nu }_{1}\rightarrow {\nu }{4}\ =\ {e}_{6}\ +\ {e}_{9}\ =\ 1\ +\ 3\ =\ 4\\{\nu }_{1}\rightarrow {\nu }{5}\ =\ {e}_{6}\ +\ {e}_{5}\ =\ 1\ +\ 2\ =\ 3\\{\nu }_{1}\rightarrow {\nu }{6}\ =\ {e}_{6}\ =\ 1\\$

Про v1 - v6 - v5 - v4, слишком много точек проходить и много поворотов соответственно.
А здесь, по моему мнению, всего один поворот и две прямых.

@3D Homer · 04.07.2016, 00:02

Нехорошо писать $https://www.cyberforum.ru/cgi-bin/latex.cgi?e_6+e_9=1+3$ , потому что $https://www.cyberforum.ru/cgi-bin/latex.cgi?e_6$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?e_9$ — это ребра, то есть пары вершин. Их нельзя складывать и они не могут быть равны числу. Но со значениями кратчайших расстояний я согласен.

Сообщение от t0lyan

Про v1 - v6 - v5 - v4, слишком много точек проходить и много поворотов соответственно.

Нужно отталкиваться от определений. Вам нужно найти "кратчайший маршрут", то есть маршрут наименьшей длины. Что такое длина маршрута? Обычно она определяется как сумма длин ребер, входящих в маршрут. Согласно такому определению длины маршрутов v1 - v6 - v5 - v4 и v1 - v6 - v4 одинаковы и оба маршрута являются кратчайшими. Если вы измените определение длины маршрута, например, чтобы оно учитывало количество ребер, то ваш ответ может быть единственным. Собственно, в задаче требовалось найти один кратчайший маршрут, а не все, поэтому ваш ответ правильный.

@t0lyan · 04.07.2016, 12:10 **[ТС]**

Нашел способ, которым описывают в задании (алгоритм Дейкстры).

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix} \nu \ & \ {\nu }_{2} \ & \ {\nu }_{3} \ & \ {\nu }_{4} \ & \ {\nu }_{5} \ & \ {\nu }_{6} \ \\ {0}^{*} \ & \ \infty \ & \ \infty \ & \ \infty \ & \ \infty \ & \ \infty \ \\ {0}^{*} \ & \ {3}^{*} \ & \ {2}^{*} \ & \ 7 \ & \ \infty \ & \ {1}^{*} \ \\ {0}^{*} \ & \ {3}^{*} \ & \ {2}^{*} \ & \ 4 \ & \ {3}^{*} \ & \ {1}^{*} \ \\ {0}^{*} \ & \ {3}^{*} \ & \ {2}^{*} \ & \ {4}^{*} \ & \ {3}^{*} \ & \ {1}^{*} \ \\ \end{matrix}$

Добавлено через 1 минуту
Отсюда известны, и кратчайшие пути ко всем точкам и к четвёртой в частности.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2

	Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа 02.07.2016, 19:52. Показов 4701. Ответов 5 Метки нет (Все метки) Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа. Указать кратчайший маршрут из вершины v1 в вершину v4. Миниатюры 0

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2
	02.07.2016, 20:12 [ТС]
	По поводу коротких путей: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\nu }_{1} \ \rightarrow {\nu }{2} \equiv {e}_{1} \\{\nu }_{1} \ \rightarrow {\nu }{3} \equiv {e}_{10} \\{\nu }_{1} \ \rightarrow {\nu }{4} \equiv {e}_{6}, {e}_{9} \\{\nu }_{1} \ \rightarrow {\nu }{5} \equiv {e}_{6}, {e}_{5} \\{\nu }_{1} \ \rightarrow {\nu }{6} \equiv {e}_{6} \\$ Кратчайший путь из v1 в v4, будет через направления е6 и е9... $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\nu }_{1} \ \rightarrow {\nu }{4} \equiv {e}_{6}, {e}_{9}$ 0

@3D Homer $Эксперт по математике/физике$ 5016 / 3628 / 1164 Регистрация: 01.09.2014 Сообщений: 9,790
	02.07.2016, 20:39
	По поводу всех вершин, кроме v4, условие задачи предписывает указать не кратчайшие пути, а только расстояния. Про кратчайший путь из v1 в v4 я согласен, но путь v1, v6, v5, v4 имеет ту же длину. 0

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2
	03.07.2016, 10:41 [ТС]
	Тогда так? $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\nu }_{1}\rightarrow {\nu }{2}\ =\ {e}_{1}\ =\ 3\\{\nu }_{1}\rightarrow {\nu }{3}\ =\ {e}_{10}\ =\ 2\\{\nu }_{1}\rightarrow {\nu }{4}\ =\ {e}_{6}\ +\ {e}_{9}\ =\ 1\ +\ 3\ =\ 4\\{\nu }_{1}\rightarrow {\nu }{5}\ =\ {e}_{6}\ +\ {e}_{5}\ =\ 1\ +\ 2\ =\ 3\\{\nu }_{1}\rightarrow {\nu }{6}\ =\ {e}_{6}\ =\ 1\\$ Про v1 - v6 - v5 - v4, слишком много точек проходить и много поворотов соответственно. А здесь, по моему мнению, всего один поворот и две прямых. 0

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2
	04.07.2016, 12:10 [ТС]
	Нашел способ, которым описывают в задании (алгоритм Дейкстры). $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{matrix} \nu \ & \ {\nu }_{2} \ & \ {\nu }_{3} \ & \ {\nu }_{4} \ & \ {\nu }_{5} \ & \ {\nu }_{6} \ \\ {0}^{} \ & \ \infty \ & \ \infty \ & \ \infty \ & \ \infty \ & \ \infty \ \\ {0}^{} \ & \ {3}^{} \ & \ {2}^{} \ & \ 7 \ & \ \infty \ & \ {1}^{} \ \\ {0}^{} \ & \ {3}^{} \ & \ {2}^{} \ & \ 4 \ & \ {3}^{} \ & \ {1}^{} \ \\ {0}^{} \ & \ {3}^{} \ & \ {2}^{} \ & \ {4}^{} \ & \ {3}^{} \ & \ {1}^{} \ \\ \end{matrix}$ Добавлено через 1 минуту Отсюда известны, и кратчайшие пути ко всем точкам и к четвёртой в частности. 0