[/b/] [/d/] [/tu/] [/a/] [/ph/] [/wa/] [/cg/] [/t/] [/p/]

[Burichan] [Foliant] [Futaba] [Greenhell] [Gurochan] [Photon] - [Home] [Manage] [Archive]
[Return]
Posting mode: Reply
Leave these fields empty (spam trap):
Name
Link
Subject
Comment
File
Verification
Password (for post and file deletion)
  • Supported file types are: GIF, JPG, PDF, PNG
  • Maximum file size allowed is 20480 KB.
  • Images greater than 200x200 pixels will be thumbnailed.
File: 1381528918876.gif -(8321 B, 333x363) Thumbnail displayed, click image for full size.
8321 No.97916  

Как проще всего доказать отсутствие пути из одной вершины в другую?

граф неориентированный и с петлями

>> No.97917  
File: 1381530053123.jpg -(672662 B, 1200x1647) Thumbnail displayed, click image for full size.
672662

>>97916
Алгоритм Дейкстры же.

>> No.97918  

>>97917 спасибо

>> No.97950   
вообще-то проще чем у Дейкстры можно:
помечаем исходную вершину как "доступную"
шаг:
  если нет доступных вершин:
    проверяем нет ли искомой среди недоступных
  иначе:
    для каждой доступной:
       помечаем всех соседей как "доступные"
    выкидываем вершины которые были "доступны" на начало шага
    повторяем процесс с оставшимися
>> No.98002  

>>97916
Доказав NP-completeness

>> No.98011  

>>97950
Для эффективности нужно использовать очередь. Пусть начальная вершина *s*, а конечная *e*.

  1. Помечаем все вершины как нерассмотренные.
  2. Добавляем вершину *s* в очередь и помечаем ее как рассмотренную.
  3. Достаем вершину из очереди, обозначим ее *h*. Если в очереди больше нет вершин, то завершаем алгоритм и вершина *e* недостижима из вершины *s*. Если *h* = *e*, то завершаем алгоритм и вершина *e* достижима из вершины *s*.
  4. Все смежные с *h* нерассмотренные вершины помечаем как рассмотренные.
  5. Переходим к шагу 3.

Delete Post []
Password

[/b/] [/d/] [/tu/] [/a/] [/ph/] [/wa/] [/cg/] [/t/] [/p/]

- wakaba 3.0.7 + futaba + futallaby -