https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D0%BF%D1%83%D1%82%D0%B5%D0%B9_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5 2026-05-03T18:05:56Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D0%BF%D1%83%D1%82%D0%B5%D0%B9_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5&diff=1181&oldid=prev 2008-10-23T16:48:17Z

<p>1 версия</p> <p><b>Новая страница</b></p><div>Задача поиска кратчайших путей в графе (''Shortest Path Problem''), заключается в следующем:<br /> <br /> Заданы ''n'' вершин графа (узлов сети) &lt;m&gt;v_1,v_2,\ldots,v_n&lt;/m&gt; и целые длины<br /> дуг &lt;m&gt;d_{ij} \equiv d(v_i,v_j)&lt;/m&gt; между ними. Чему равна наименьшая возможная длина пути, ведущего из ''v&lt;sub&gt;1&lt;/sub&gt;'' в ''v&lt;sub&gt;k&lt;/sub&gt;'', для всех &lt;m&gt;k \in (2 \ldots n)&lt;/m&gt;? <br /> <br /> Если длины дуг неотрицательны, то можно использовать [[алгоритм Дейкстры]], если есть отрицательные длины, но нет циклов отрицательного веса (если такие циклы есть — то оптимального решения очевидно не существует), то можно использовать [[алгоритм Флойда-Уоршолла]].<br /> <br /> <br /> [[Category:Задачи]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

WikiSysop