48
правок
Изменения
Нет описания правки
==Реализация==
Реализуем данный алгоритмследующим образом: рассмотрим вершину i. Будем пересчитывать d для всех вершин, выходящих из i:
//w - матрицы как в описании, d - массив как в описании, p - массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br />
inputData() //считывание данных <br />
| || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
|-
| '''1''' || 0 - || - || - || 5 || - || - || - || -
|-
| '''2''' || 1 || 0 - || 1 || - || 4 || 3 || - || -
|-
| '''3''' || - || - || 0 - || - || - || 1 || - || -
|-
| '''4''' || - || - || - || 0 - || - || - || - || -
|-
| '''5''' || - || - || - || 3 || 0 - || - || - || 1
|-
| '''6''' || - || - || - || 5 || - || 0 - || 2 || -
|-
| '''7''' || - || - || - || 2 || - || - || 0 - || -
|-
| '''8''' || - || - || - || 1 || - || - || - || 0 -
|}
Требуется найти путь из '''2''' в '''4'''. <br />
==Источники==
*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе]
*[http://neerc[Динамическое_программирование#.ifmoD0.ru/mediawiki/index9F.php/%D0%9F%D1%.80%.D0%.B8%.D0%.BD%.D1%.86%.D0%.B8%.D0%.BF_%.D0%.BE%.D0%.BF%.D1%.82%.D0%.B8%.D0%.BC%.D0%.B0%.D0%.BB%.D1%.8C%.D0%.BD%.D0%.BE%.D1%.81%.D1%.82%.D0%.B8_%.D0%.BD%.D0%.B0_%.D0%.BF%.D1%.80%.D0%.B5%.D1%.84%.D0%.B8%.D0%.BA%.D1%.81%.D0%.B5 |Принцип оптимальности на префиксе]]
* [http://en.wikipedia.org/wiki/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
[[Категория: Динамическое программирование]] [[Категория: Дискретная математика и алгоритмы]]
