Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.10.2010, 13:21
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

Мне нужен поиск кратчайшего пути или нет?
Есть неориентированный плоский взвешенный граф состоящий из одной грани (если не считать внешнюю). Т.е. по сути это кольцо из произвольного количества ребер (больше 3). В этом графе выбираются 2 произвольных вершины, не принадлежащих одному ребру и нужно посчитать кратчайший путь между этими вершинами.

Есть ли в этом случае способ посчитать путь быстрее чем, скажем алгоритмом Дейкстры?
З.Ы. мне нужен маршрут, а не длина пути.
  #2  
Старый 27.10.2010, 14:15
гость

 
Сообщений: n/a

Сообщение от Bonus Посмотреть сообщение
Есть ли в этом случае способ посчитать путь быстрее чем, скажем алгоритмом Дейкстры?
а там всего два пути. считаешь длину обоих как угодно абсолютно и берешь минимум
  #3  
Старый 27.10.2010, 15:23
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

Будет ли верным утверждение, что кратчайший путь в данном случае тот, в котором меньше вершин или ребер? Т.е. учесть просто КОЛИЧЕСТВО, а не веса.
  #4  
Старый 27.10.2010, 15:27
гость

 
Сообщений: n/a

Сообщение от Bonus Посмотреть сообщение
Будет ли верным утверждение, что кратчайший путь в данном случае тот, в котором меньше вершин или ребер? Т.е. учесть просто КОЛИЧЕСТВО, а не веса.
слушайте, вы сами уж определителитесь, взвешенный у вас граф или нет, учитывать веса ребер в нем или нет. как определитесь, такой и будет алгоритм.
  #5  
Старый 27.10.2010, 15:51
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

Граф-то взвешенный, но мне нужен наиболее быстрый алгоритм. А веса в моем случае это реальная длина ребер.
  #6  
Старый 27.10.2010, 16:36
гость

 
Сообщений: n/a

Сообщение от Bonus Посмотреть сообщение
Граф-то взвешенный, но мне нужен наиболее быстрый алгоритм.
Кака разница делать += 1 или += edge.weight? И то и то одинаково быстро. Боттлнек не в CPU будет, а в памяти или диске скорее всего.
  #7  
Старый 27.10.2010, 18:29
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

я имел ввиду, что сначала можно узнать с какой стороны вершин меньше, а потому уже делать +=edge.weight только в этом направлении.
  #8  
Старый 27.10.2010, 22:31
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск пути в неориентированном графе Sanyco-007 Графы 1 14.09.2010 21:40
Поиск кратчайшего пути гость Вычислительная геометрия 8 27.05.2010 19:57
Многократный поиск кратчайшего пути в графе. artem_k Графы 12 10.05.2010 13:39
Поиск кратчайшего пути во взвешенном графе с заданным количеством вершин или ребер Mitrich Графы 9 24.07.2009 18:21
Поиск кратчайшего пути в бесконтурном графе гость Реализация, исходники, языки 1 06.06.2009 10:27