2015-07-14
441
Як було зазначено, алгоритм Данцига можна розбити на три незалежні кроки:
1. Пошук найкоротшого шляху 
.
2. Пошук найкоротшого шляху 
.
3. Пошук найкоротшого шляху 
.
Важливо відзначити, що крок 3 може бути виконаний лише після повного завершення двох попередніх. Перші два кроки схематично зображено на [слайд на стор. 17, Lect_7.pdf]. Як бачимо, для обрахунку нового елемента () слід опрацювати цілий стовпчик (рядок) під матриці 
(стрілками позначено дані, які слід прочитати для знаходження відповідного елемента). Отже, при плануванні роботи кількох потоків, оптимальним буде саме таке розбиття вхідних даних, що дозволить уникнути зайвого обміну інформацією між потоками, а також зменшити затрати на синхронізацію.
