Алгоритъм на Дейкастра при ацикличен граф

Алгоритъм на Дейкастра при ацикличен граф.

Ако знаем че графът е ацикличен можем да подобрим алг.на Дейкстра, като определим еднозначно последователността на избор на връх за обхождане. Това е последователността, съотв.на топологичната подредба. Алг.базиран на подреден топологично граф, се обработва за един пас. Това се дължи на факта, че пътят до избран според топологичната подредба връх не може вече да се намали, защото към него няма входящи ребра от необходени върхове. По този начин отпада необх.от приоритетна опашка и оценката на алг. е O(│E│+│V│).

Може да се посочат различни пр. от практиката: как да достигнем макс. бързо до дадена точка като се движим само в една посока. Друг възможен пример е моделиране на химич. реакция, в която се отделя енергия, т.е. движението е само в една посока от
по-високо към по-ниско енергийно ниво. Най-важен пример за нас е оценката на дейности и анализ на критичния път.Посредством разглеждане на граф на дейностите необх. за завършване на софтуерен проект. Мд отговорим на следните въпроси:

• 
  Кое е мин време за завърш на проекта;
  
• 
  Колко мд закъсняват отделните дейности, без това да се отрази на крайния срок.
  

В графът на дейностите всеки връх пред-ставя дейност, която трд се изпълни като е посочено и времето, което заема тя.Ребрата показват реда на изпълн. на дейностите. Графът е ацикличен и освен това допуска работа в паралелизъм за
независещи една от друга дейности.За да решим поставената зад.трд преобразуваме графа на дейностите в граф на събитията.При това всяко съби-тие отговаря на завършване на дейност и всички зависещи от нея дейности. За да се