Daa15 Shortestpath
Най-къси пътища в графи. Примери за приложения. Потенциални трудности при наличието на отрицателни тегла. Анализ на задачата и сравнението и със задачата за най-дълъг път в граф. Алгоритъм на Дейкстра за намиране на най-късите пътища от даден връх до всички останали върхове. Анализ на корекността и сложността по време на този алгоритъм.
Най-къс път в граф
Алгоритъм на Дейкстра
Добро обяснение на алгоритъма може да се намери в Wikidot - http://fmi.wikidot.com/tg2#toc2
Алгоритъм на Floyd-Warshal
Намира най-късите пътища между всяка двойка върхове., като работи и с отрицателни ребра.
for (k=0; k<N; ++k) for (i=0; i<N; ++i) for (j=0; j<N; ++j) if (A[i][j]>A[i][k]+A[k][j]) A[i][j]=A[i][k]+A[k][j];
page revision: 1, last edited: 31 May 2011 23:51