Алгоритмы на графах. Литература.

[B@R5uk]

Посоветуйте, пожалуйста, литературу посвящённую алгоритмам на графах. Желательно что-нибудь доступное, без заумной математики и с примерами кода. Можно на английском. Поиск путей (в том числе и кратчайшего) наверняка не единственная задача, связанная с графами. Хотелось бы ознакомиться с тем, что народ до сих пор напридумывал в этой области. Заранее очень благодарен.

[Sender]

Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение.

[B@R5uk]

Спасибо за быстрый ответ. Скачаю, ознакомлюсь.

Можно сразу вопрос до кучи, чтобы темы не плодить? У меня имеется планарный граф и я хочу найти все возможные различные пути из вершины А в вершину Б. Под различными понимаются такие пути, каждый из которых содержит вершину, которую не содержит другой путь. Если же имеется два пути, допустим S и R, причём множество вершин пути S является подмножеством вершин пути R, то такие два пути являются эквивалентными, и в ответ выбирается, разумеется, самый короткий путь S.

Например, вот эти два пути различны:

    #####           #####
    #...#           #...#
    #...#           #...#
  ###...##        ###...##
  #......#        #......#
###.#.##.###    ###.#.##.###
#...#.##...#    #...#.##...#
#.S>>>>>>E.#    #.S>>v.>>E.#
#####.#....#    #####v#^...#
    #...####        #>>^####
    #####           #####

А вот здесь первые три эквивалентны, причём предпочтение отдаётся самому левому, в то время как четвёртый отличается от первых трёх:

    #####           #####           #####           #####
    #...#           #...#           #...#           #...#
    #...#           #...#           #...#           #...#
  ###...##        ###>v.##        ###.>v##        ###>>v##
  #..>>>v#        #..^>>v#        #..>^>v#        #..^.>v#
###.#^##v###    ###.#^##v###    ###.#^##v###    ###.#^##v###
#...#^##v..#    #...#^##v..#    #...#^##v..#    #...#^##v..#
#.S>>^..>E.#    #.S>>^..>E.#    #.S>>^..>E.#    #.S>>^..>E.#
#####.#....#    #####.#....#    #####.#....#    #####.#....#
    #...####        #...####        #...####        #...####
    #####           #####           #####           #####

В каком направлении копать?

[Pavia]

Окулов С.М.-Программирование в алгоритмах. БИНОМ. Лаборатория знаний (2014)

[Paragraph]

"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002. ISBN 978-3-662-04921-1
доступно написана и использует literate programming, т.е. код, его спецификация и документация представляют собой единый документ. Не уверен, есть ли где pdf для "ознакомления" (у меня физическая копия). Если найдете pdf, буду признателен, если дадите знать в ЛС.

[B@R5uk]

Pavia в сообщении #1270023 писал(а):

Окулов С.М.-Программирование в алгоритмах. БИНОМ. Лаборатория знаний (2014)

Большое спасибо! В числе прочего, в главе про комбинаторику нашёл решение задачи, над которой давно ломал голову: восстановить перестановку по её порядковому номеру. Решение на столько простое, что мне даже стыдно, что я сам не смог додуматься.

Paragraph, предложенную вами книгу при быстром осмотре в электронном виде не нашёл. Когда будет доступ к безлимитному интернету попробую более тщательный поиск.

[Aritaborian]

Paragraph в сообщении #1270078 писал(а):

"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002.

http://b-ok.org/book/2099958/2128a6.

[B@R5uk]

Aritaborian, спасибо.

Для задачки выше, я таки построил некий алгоритм. Он находит все возможные различные пути из заданной точки в каждую другую. Для графа, получающегося из карты на картинке выше для разных точек выходит от 1000 до 5000 вариантов. Вот, думаю, не многовато ли?

[Paragraph]

Цитата:

Paragraph в сообщении #1270078 писал(а):
"Algorithms on Trees and Graphs", Gabriel Valiente, Springer 2002.
http://b-ok.org/book/2099958/2128a6.

Спасибо за ссылку!

[Aritaborian]

Paragraph в сообщении #1270595 писал(а):

Спасибо за ссылку!

B@R5uk в сообщении #1270246 писал(а):

Aritaborian, спасибо.

Места надо знать ;-D