https://lib.custis.ru/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
Алгоритм Дейкстры - История изменений
2026-06-12T18:31:45Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=27271&oldid=prev
StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»
2011-06-13T17:43:22Z
<p>Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»</p>
<a href="https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=27271&oldid=9957">Внесённые изменения</a>
StasFomin
https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=9957&oldid=prev
WikiSysop: 1 версия
2008-10-23T16:47:53Z
<p>1 версия</p>
<table class='diff diff-contentalign-left'>
<tr style='vertical-align: top;' lang='ru'>
<td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 16:47, 23 октября 2008</td>
</tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div>
</td></tr></table>
WikiSysop
https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=9956&oldid=prev
StasFomin: обновление данных
2008-10-22T15:35:43Z
<p>обновление данных</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 15:35, 22 октября 2008</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи [[Поиск кратчайших путей в графе]].</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи [[Поиск кратчайших путей в графе]].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от ''v'' до ''w'', проходящий через вершину ''y'', назовем его <<del class="diffchange diffchange-inline">math</del>>(v \rightarrow w)^*</<del class="diffchange diffchange-inline">math</del>>, то его первая часть от ''v'' до ''y'', <<del class="diffchange diffchange-inline">math</del>>(v \rightarrow y)^*</<del class="diffchange diffchange-inline">math</del>>, тоже будет кратчайшим путем. Действительно, если бы это было не так, т.е. существовал бы путь <<del class="diffchange diffchange-inline">math</del>>(v \rightarrow y)^!</<del class="diffchange diffchange-inline">math</del>> длины меньшей, чем <<del class="diffchange diffchange-inline">math</del>>(v \rightarrow y)^*</<del class="diffchange diffchange-inline">math</del>>, то можно было бы улучшить оптимальный путь <<del class="diffchange diffchange-inline">math</del>>(v \rightarrow w)^*</<del class="diffchange diffchange-inline">math</del>>, заменив в нем <<del class="diffchange diffchange-inline">math</del>>(v \rightarrow y)^*</<del class="diffchange diffchange-inline">math</del>> на <<del class="diffchange diffchange-inline">math</del>>(v \rightarrow y)^!</<del class="diffchange diffchange-inline">math</del>>  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от ''v'' до ''w'', проходящий через вершину ''y'', назовем его <<ins class="diffchange diffchange-inline">m</ins>>(v \rightarrow w)^*</<ins class="diffchange diffchange-inline">m</ins>>, то его первая часть от ''v'' до ''y'', <<ins class="diffchange diffchange-inline">m</ins>>(v \rightarrow y)^*</<ins class="diffchange diffchange-inline">m</ins>>, тоже будет кратчайшим путем. Действительно, если бы это было не так, т.е. существовал бы путь <<ins class="diffchange diffchange-inline">m</ins>>(v \rightarrow y)^!</<ins class="diffchange diffchange-inline">m</ins>> длины меньшей, чем <<ins class="diffchange diffchange-inline">m</ins>>(v \rightarrow y)^*</<ins class="diffchange diffchange-inline">m</ins>>, то можно было бы улучшить оптимальный путь <<ins class="diffchange diffchange-inline">m</ins>>(v \rightarrow w)^*</<ins class="diffchange diffchange-inline">m</ins>>, заменив в нем <<ins class="diffchange diffchange-inline">m</ins>>(v \rightarrow y)^*</<ins class="diffchange diffchange-inline">m</ins>> на <<ins class="diffchange diffchange-inline">m</ins>>(v \rightarrow y)^!</<ins class="diffchange diffchange-inline">m</ins>>  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>(См. [[#Рисунок 1]]).</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>(См. [[#Рисунок 1]]).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
StasFomin
https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=9783&oldid=prev
WikiSysop: 1 версия
2008-08-04T09:55:51Z
<p>1 версия</p>
<table class='diff diff-contentalign-left'>
<tr style='vertical-align: top;' lang='ru'>
<td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 09:55, 4 августа 2008</td>
</tr><tr><td colspan='2' style='text-align: center;' class='diff-multi' lang='ru'>(не показана 1 промежуточная версия 1 участника)</td></tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div>
</td></tr></table>
WikiSysop
https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=2791&oldid=prev
BenderBot: реплицировано из внутренней CustisWiki
2007-03-06T04:53:39Z
<p>реплицировано из внутренней CustisWiki</p>
<a href="https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=2791">Внесённые изменения</a>
BenderBot
https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=9782&oldid=prev
StasFomin: /* Трассировка алгоритма */
2007-03-05T12:56:34Z
<p><span dir="auto"><span class="autocomment">Трассировка алгоритма</span></span></p>
<a href="https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=9782&oldid=8946">Внесённые изменения</a>
StasFomin
https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=8946&oldid=prev
BenderBot: реплицировано из внутренней CustisWiki
2005-12-06T04:40:26Z
<p>реплицировано из внутренней CustisWiki</p>
<a href="https://lib.custis.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B&diff=8946&oldid=2791">Внесённые изменения</a>
BenderBot