Алгоритм Дейкстры - IU9 BMSTU Wiki (original) (raw)

Алгоритм Дейкстры

Поиск кратчайшего пути между двумя вершинами в графе.

Реализация на основе очереди с приоритетами. Сложность порядка O(nlog(n))O(n\log(n))O(nlog(n)).

#include #include #include using namespace std;

typedef vector vi; typedef pair<int,int> ii; typedef vector vii; typedef vector vvii;

const int MAX = 1001; const int MAXINT = 1000000000;

int n; vvii G(MAX); vi D(MAX, MAXINT);

void Dijkstra(int s) { set Q; D[s] = 0; Q.insert(ii(0,s));

while(!Q.empty())
{
    ii top = *Q.begin();
    Q.erase(Q.begin());
    int v = top.second;
    int d = top.first;

    for (vii::const_iterator it = G[v].begin(); it != G[v].end(); it++)
    {
        int v2 = it->first;
        int cost = it->second;
        if (D[v2] > D[v] + cost)
        {
            if (D[v2] != 1000000000)
            {
                Q.erase(Q.find(ii(D[v2], v2)));
            }
            D[v2] = D[v] + cost;
            Q.insert(ii(D[v2], v2));
        }
    }
}

}

int main() {

int m, s, t = 0;
scanf("%d %d %d %d", &n, &m, &s, &t);

for (int i = 0; i < m; i++)
{
    int a, b, w = 0;
    scanf("%d %d %d", &a, &b, &w);
    G[a - 1].push_back(ii(b - 1, w));
    G[b - 1].push_back(ii(a - 1, w));
}

Dijkstra(s - 1);

printf("%d\n", D[t - 1]);

return 0;

}

Click here to edit contents of this page.

Click here to toggle editing of individual sections of the page (if possible). Watch headings for an "edit" link when available.

Append content without editing the whole page source.

Check out how this page has evolved in the past.

If you want to discuss contents of this page - this is the easiest way to do it.

View and manage file attachments for this page.

A few useful tools to manage this Site.

See pages that link to and include this page.

Change the name (also URL address, possibly the category) of the page.

View wiki source for this page without editing.

View/set parent page (used for creating breadcrumbs and structured layout).

Notify administrators if there is objectionable content in this page.

Something does not work as expected? Find out what you can do.

General Wikidot.com documentation and help section.

Wikidot.com Terms of Service - what you can, what you should not etc.

Wikidot.com Privacy Policy.