Построить граф, определить кратчайший путь алгоритмом Дейкстры

@Almareta · Регистрация: 19.03.2009

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

В задании требуется по матрице весов построить граф (см ниже) дальше определить кратчайший путь по алгоритму Дейкстры.
Как строить граф по матрице смежности нашла, с матрицей весов хуже.Помогите кто чем может )

vetvet · 12.03.2011, 19:30

так же, только соответствующему ребру ещё и приписывается указанный вес.

@Almareta · 12.03.2011, 19:34 **[ТС]**

Ещё вопрос, правильно ли я понимаю(скорее всего нет).х-ы по горизонтали точки из которых строим, х-ы по вертикали куда?

vetvet · 12.03.2011, 23:09

скорее всего. это должно быть оговорено в лекциях или рекомендованной литературе.

@Хохол · 12.03.2011, 23:10

У вас граф-то неориентированный. Ну если ориентированный, то очень симметричный.

vetvet · 12.03.2011, 23:52

Хохол, действительно, чёт я не обратила внимания.

Almareta, если на пересечении горизонтального х и вертикального стоит цифра, просто соединяете их без стрелки и подписываете соответствующий вес. как на картинке:

@Almareta · 13.03.2011, 14:50 **[ТС]**

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

@Almareta · 11.05.2011, 08:21 **[ТС]**

Решила вроде по алгоритму дейкстры. Дерево графа не получилось по моему. Прошу пожалуйста проверить.

@Хохол · 11.05.2011, 09:00

Дерево действительно не получилось. В дереве не должно быть циклов.

@Almareta · 11.05.2011, 09:08 **[ТС]**

так вот и хотелось бы вкратце узнать почему и где ошибка....

@Almareta · 12.05.2011, 09:41 **[ТС]**

Есть сайт для решения алгоритмом Дейкстры. Так вот он на мой граф выдал следующий результат.
У меня сомнения уже на второй итерации

@Almareta Юный падаван 17 / 17 / 0 Регистрация: 19.03.2009 Сообщений: 253
		1
	Построить граф, определить кратчайший путь алгоритмом Дейкстры 12.03.2011, 19:24. Показов 9210. Ответов 10 Метки нет (Все метки) В задании требуется по матрице весов построить граф (см ниже) дальше определить кратчайший путь по алгоритму Дейкстры. Как строить граф по матрице смежности нашла, с матрицей весов хуже.Помогите кто чем может ) Миниатюры 0

vetvet Змеюка одышечная 9864 / 4595 / 178 Регистрация: 04.01.2011 Сообщений: 8,556
	12.03.2011, 19:30	2
	так же, только соответствующему ребру ещё и приписывается указанный вес. 1

@Almareta Юный падаван 17 / 17 / 0 Регистрация: 19.03.2009 Сообщений: 253
	12.03.2011, 19:34 [ТС]	3
	Ещё вопрос, правильно ли я понимаю(скорее всего нет).х-ы по горизонтали точки из которых строим, х-ы по вертикали куда? 0

vetvet Змеюка одышечная 9864 / 4595 / 178 Регистрация: 04.01.2011 Сообщений: 8,556
	12.03.2011, 23:09	4
	скорее всего. это должно быть оговорено в лекциях или рекомендованной литературе. 1

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	12.03.2011, 23:10	5
	У вас граф-то неориентированный. Ну если ориентированный, то очень симметричный. 1

vetvet Змеюка одышечная 9864 / 4595 / 178 Регистрация: 04.01.2011 Сообщений: 8,556
	12.03.2011, 23:52	6
	Хохол, действительно, чёт я не обратила внимания. Almareta, если на пересечении горизонтального х и вертикального стоит цифра, просто соединяете их без стрелки и подписываете соответствующий вес. как на картинке: Миниатюры 1

@Almareta Юный падаван 17 / 17 / 0 Регистрация: 19.03.2009 Сообщений: 253
	13.03.2011, 14:50 [ТС]	7
	Спасибо, граф как то нарисовала, сейчас с алгоритмом буду разбираться. 0

@Almareta Юный падаван 17 / 17 / 0 Регистрация: 19.03.2009 Сообщений: 253
	11.05.2011, 08:21 [ТС]	8
	Решила вроде по алгоритму дейкстры. Дерево графа не получилось по моему. Прошу пожалуйста проверить. Миниатюры 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	11.05.2011, 09:00	9
	Дерево действительно не получилось. В дереве не должно быть циклов. 1

@Almareta Юный падаван 17 / 17 / 0 Регистрация: 19.03.2009 Сообщений: 253
	11.05.2011, 09:08 [ТС]	10
	так вот и хотелось бы вкратце узнать почему и где ошибка.... 0

	12.05.2011, 09:41