Найти цепочку пар чисел соединяющую две пары чисел

[green_guy]

Дана пара (230, 35), (301, 908). Найти самую короткую цепочку к ней из множества пар:
(230, 37), (230,35), (35, 660), (35, 54), (849, 301),(660, 849), ...(263, 754). Здесь ответом будет (если не учитывать многоточие): (35, 660) (660, 849) (849, 301).
Простейший алгоритм перебором ясен, хочется чего-нибудь эдакого... Реализация будет на perl.
Ссылки на не очень абстрактные онлайн мануалы по подобным задачам принимаю.

[elide]

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

[green_guy]

Действительно графы.
Тут есть ещё такой страх. Летом у меня сгорел винт. И я теперь боюсь как бы не напрограммировать себе ещё такого удовольствия. Если я буду тупо хранить узлы в файле, то при переборе (многократном проходе файла), мне кажется, головка винта будет ненормально дёргаться. Я правильно боюсь? И как с такой паранойей к гуглу обращаться?
P.S. "йей" - что-то новенькое

[Zeus]

Если я буду тупо хранить узлы в файле, то при переборе (многократном проходе файла), мне кажется, головка винта будет ненормально дёргаться. Я правильно боюсь? И как с такой паранойей к гуглу обращаться?

Во-первых, обрабатывать данные "на винте" - это что-то новенькое. В память их!
Во-вторых, там от твоего read/write до собственно головки винта ещё столько всего программно-аппаратного, что, думаю, можно говорить только о некоторой корреляции движения головки и вывозов твоих функций чтения-записи.

[green_guy]

Спасибо. Знаю. А что если память не резиновая? А что если read/write без буферизации? (Хотя у винта есть свой буфер.) Интересует вообще эта тема: "Чего нельзя кодить, чтобы не было проблем с железом".
Лучше скажите что почитать, а выводы я и сам сделаю.

[elide]

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

и, это... чтобы не было проблем с железом - лучше вообще ничего не кодить. больше скажу - лучше вообще комп не покупать...

[green_guy]

Проехали. Читаю Ахо, Хопкрофта, Ульмана. Там всё есть.

да не покупал я его. подарили...

[flook]

А что если read/write без буферизации?

Кто научит меня отключать страничный кеш в ядре?.. Никто? <_<