# data[].attributes.body
*Зошто се важни алгоритмите за најкраток пат?

*Краток преглед на предходните методи (BFS, Dijkstra).

# data[].attributes.headline
На сликата е претставе

# data[].attributes.body
На сликата е претставен алгоритамот Дикстра.Ребрата се со позитивна вредност/тежина.

# data[].attributes.headline
Преставен е BFS.Гледам

# data[].attributes.body
Преставен е BFS.Гледаме дека ребрата имаат иста

тежина.

# data[].attributes.headline
BFS-кој се користи ког

# data[].attributes.body
BFS-кој се користи кога сите ребра во графот имаат иста тежина

Dijkstra- најкраткиот пат од едно теме до останатитe.

Floyd-Warshall:  најкраткиот пат помеѓу сите парови на темиња во графот (а не само од едно теме –  како кај Dijkstra).

Bellman-Ford е сличен на Dijkstra, но  се користи кога во графот може да постојат и ребра со негативни тежини.

# data[].attributes.headline
Разлики помеѓѕ Djikstra и Floyd-Warshall алгоритамот.

# data[].attributes.subject
Разлики помеѓѕ Djikstra и Floyd-Warshall алгоритамот.

# data[].attributes.body
Тип на проблем:

Dijkstra: Се користи за наоѓање на најкратки патишта од едно изворно теме до сите други.

Floyd-Warshall: Се користи за наоѓање на најкратки патишта од сите темиња до сите темиња.

Принцип:

Dijkstra: Гради најкратки патишта постепено.

Floyd-Warshall: Користи динамичко програмирање со матрица на растојанија.

Структура на податоци:

Dijkstra: Обично користи приоритетна опашка (heap или queue).

Floyd-Warshall: Користи матрица со димензии n × n.

Негативни тежини:

Dijkstra: Не дозволува негативни тежини.

Floyd-Warshall: Дозволува негативни тежини, но не дозволува негативни циклуси.

Сложеност (време):

Dijkstra: Има временска сложеност O((V + E) log V) за едно извршување.

Floyd-Warshall: Има временска сложеност O(V³).

Примена:

Dijkstra: Се користи за наоѓање на најкратки патишта од една одредена локација.

Floyd-Warshall: Се користи за целосна анализа на сите патишта во графот.

Повеќекратно користење:

Dijkstra: Мора да се повика посебно за секое изворно теме.

Floyd-Warshall: Доволно е еднаш да се изврши, и потоа дава одговор за сите парови на темиња.

# data[].attributes.headline
Кога да се користат

# data[].attributes.subject
Кога да се користат

# data[].attributes.body
Dijkstra

-----------------------------------

Кога ти треба најкраткиот пат од едно теме (на пр. во GPS навигација).

Кога графот е голем и нема негативни тежини.

Floyd-Warshall

------------------------------------

Кога ти требаат сите најкратки патишта (на пр. во мрежна анализа, комуникациски мрежи).

Кога графот е густ (многу ребра), и бројот на темиња не е преголем.

# data[].attributes.body
Во оваа видео детално е објаснето како функционира алгоритамот.Истото го објаснивме и на часот.

# data[].attributes.body
Ако имаме граф со n јазли, алгоритмот го пресметува најкраткиот пат од секој јазол i до секој друг јазол j, користејќи сите можни јазли k како потенцијални посредници.

Чекори на алгоритмот:

-------------------------------

1. Иницијализација:

Креирај матрица dist[n][n] каде секоја вредност dist[i][j] е:

0 ако i == j

тежината на директната врска од i до j, ако постои

бесконечност (∞), ако нема директна врска

2. псевдо код;

за секој јазол k од 0 до n-1:

за секој јазол i од 0 до n-1:

за секој јазол j од 0 до n-1:

ако dist[i][j] > dist[i][k] + dist[k][j]:

тогаш dist[i][j] = dist[i][k] + dist[k][j]

3. Ова значи: ако патот од i до j преку k е пократок од досега познатиот, го подобруваме.

4. Резултат:

По извршувањето, матрицата dist ќе содржи најкратки растојанија меѓу сите парови i, j.

# data[].attributes.body
Имај граф со 3 јазли и следниве врски:

0 → 1 = 4

0 → 2 = 11

1 → 2 = 2

Иницијална матрица:

dist = [ [0, 4, 11], [∞, 0, 2], [∞, ∞, 0] ]

По извршување:

dist[0][2] ќе се подобри на 4 + 2 = 6 (од 0 до 1 до 2)

Финална матрица:

[ [0, 4, 6], [∞, 0, 2], [∞, ∞, 0] ]

# data[].attributes.headline
Практични Забелешки за Floyd-Warshall

# data[].attributes.subject
Практични Забелешки за Floyd-Warshall

# data[].attributes.body
Може да дојде до overflow, особено ако dist[i][k] или dist[k][j] се ∞. Во таков случај, збирот ќе биде погрешен или негативен (ако ∞ е претставено со голема конечна вредност, како 10^9).

***

Решение: пред да го пресметаш збирот, проверуваш дали обете вредности се помали од ∞.

***

Ако графот содржи негативен циклус (пат кој почнува и завршува во ист јазол со негативна вкупна тежина), Floyd-Warshall не може да се користи за да се најдат најкратки патишта, затоа што  -Растојанието може да се намалува бесконечно секогаш кога се минува низ циклусот.

***

За откривање негативен циклус: ако по извршување на алгоритмот, dist[i][i] < 0 за некое i, тоа значи дека има негативен циклус во графот. ***

# data[].attributes.headline
Како негативните циклуси влијаат на решението

# data[].attributes.subject
Како негативните циклуси влијаат на решението

# data[].attributes.body
•Во граф со негативен циклус, можеш постојано да поминуваш низ тој циклус и сѐ повеќе да го намалуваш растојанието.

•Алгоритмот никогаш нема да стигне до стабилно решение, бидејќи секогаш постои пократок пат ако циклусот се повтори.

•На крајот, не можеш да кажеш кој е најкраткиот пат, бидејќи вредноста може да оди до -∞.

Со негативен циклус, можеш повторно и повторно да поминуваш низ истиот циклус и да го намалуваш вкупното растојание;

Алгоритмот ќе мисли дека секогаш постои подобар, пократок пат, и никогаш нема да заврши со конечни вредности

Пример:

Јазол 1 → Јазол 2 (тежина 2)

Јазол 2 → Јазол 3 (тежина -5)

Јазол 3 → Јазол 1 (тежина 1)

Вкупно: 2 + (-5) + 1 = -2

# data[].attributes.body
Како работи (на кратко):

Се иницијализираат сите растојанија како ∞, освен почетниот јазол (0).

Се вршат V-1 итерации (V = број на јазли)

На крај, се прави уште една итерација за да се провери дали постои негативен циклус (ако растојанието пак се подобрува → постои негативен циклус).

# data[].attributes.attachment_link.title
Bellman-Ford in 5 minutes — Step by step example

# data[].attributes.headline
Детали за ракување со негативни тежини и циклуси

# data[].attributes.subject
Детали за ракување со негативни тежини и циклуси

# data[].attributes.body
По извршувањето на тие |V| - 1 итерации, алгоритмот прави уште една дополнителна итерација.

Ако во таа итерација се најде дека растојанието може дополнително да се намали, тоа значи дека има негативен циклус во графот.

Во таков случај, најкраткиот пат не може да се дефинира, бидејќи може да кружи бесконечно низ тој негативен циклус и да го намалува растојанието.

Пример на негативен циклус:

Да речеме дека имаме граф со циклус:

A → B (тежина -1)

B → C (тежина -1)

C → A (тежина -1)

Севкупната тежина на циклусот е -3, што значи дека можеш бесконечно да кружиш и да го намалуваш растојанието.

# data[].attributes.headline
Пример-Кешбек

# data[].attributes.subject
Пример-Кешбек

# data[].attributes.body
Контекст: Замисли патна мрежа каде некои патишта имаат попуст или враќање на пари (како cashback или ваучер систем).

Пример:

Пат   A → B чини 10 денари.

Пат   B → C чини 5 денари.

Пат   C → A дава поврат од -20 денари (негативна тежина).

Негативен циклус:  A → B → C → A, патникот би можел да прави профит

10 + 5 – 20 = –5 денари

# data[].attributes.body
Bellman-Ford алгоритам

Тип на граф:  Ориентиран, со тежини (може и негативни).

Клучна карактеристика: Работи со негативни тежини, но не смее да има негативен циклус.

Сложеност:     O(V × E), каде V - јазли, а E- ребра.

Примена:    Ако графот има негативни тежини.

Предности:    Јасен и добар за помали графови

----------------------------

Floyd-Warshall алгоритам

Тип на граф:  Ориентиран, тежински, за сите парови на јазли.

Клучна карактеристика: Матрица која ја пресметува најкратката растојание помеѓу сите парови на јазли.

Сложеност:     O(V³)

Примена:    Кога сакаш да ги знаеш сите најкратки патеки меѓу сите јазли.

# data[].attributes.body
tashevskag@gmail.com