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

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

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

Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины 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 минуту
Отсюда известны, и кратчайшие пути ко всем точкам и к четвёртой в частности.

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2
		1
	Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа 02.07.2016, 19:52. Показов 4107. Ответов 5 Метки нет (Все метки) Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа. Указать кратчайший маршрут из вершины v1 в вершину v4. Миниатюры 0

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2
	02.07.2016, 20:12 [ТС]	2
	По поводу коротких путей: $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 $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,660
	02.07.2016, 20:39	3
	По поводу всех вершин, кроме v4, условие задачи предписывает указать не кратчайшие пути, а только расстояния. Про кратчайший путь из v1 в v4 я согласен, но путь v1, v6, v5, v4 имеет ту же длину. 0

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2
	03.07.2016, 10:41 [ТС]	4
	Тогда так? $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

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,660
	04.07.2016, 00:02	5
	Нехорошо писать $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 одинаковы и оба маршрута являются кратчайшими. Если вы измените определение длины маршрута, например, чтобы оно учитывало количество ребер, то ваш ответ может быть единственным. Собственно, в задаче требовалось найти один кратчайший маршрут, а не все, поэтому ваш ответ правильный. 0

@t0lyan 12 / 12 / 0 Регистрация: 08.05.2015 Сообщений: 155 Записей в блоге: 2
	04.07.2016, 12:10 [ТС]	6
	Нашел способ, которым описывают в задании (алгоритм Дейкстры). $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