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];
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License