Именно в Бразилии живут удавы-гувернантки... Подробнее >>
Это интересно

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

Алгоритм Дейкстры - алгоритм поиска кратчайшего пути. Его можно применять в логистике для поиска оптимальных маршрутов.


Например, если дороги рассматривать как ребра графа, а перекрестки как его вершины, то задача поиска кратчайшего пути в населенном пукнкте сводится к задаче поиска кратчайшего пути в этом графе. Сделаем формальную постановку рассматриваемой задачи. Дано: взвешенный ориентированный граф G=(V,E). Необходимо найти: цепь (последовательность соединенных между собой ребер), которая начинается в некоторой начальной точке s (исток) и оканчивается в некоторой точке f. Очевидно, что такая цепь не имеет циклов.

Алгоритм Дейкстры позволяет находить кратчайшие пути из одной вершины во все остальные. Следует заметить, что существенным ограничением этого алгоритма является недопустимость наличия ребер с отрицательным весом.

Алгоритм Дейкстры на каждом шаге добавляет к множеству S одну вершину, для которой расстояние от истока меньше, чем для остальных вершин, еще не вошедших в S. Например, на первом шаге алгоритма к множеству S всегда добавляется стартовая вершина(исток). Естественно, что именно эта вершина добавляется в множество S, так как расстояние от нее к самой себе равно нулю, что есть минимальным из расстояний от этой вершины ко всем остальным.

#include <cstdio>

using namespace std;


const int MAX=200,INF=10000;

int G[MAX][MAX],d[MAX];

bool used[MAX];

int i,j;

int n,s,f;


int min(int a,int b);

void dijkstra(int source);


int main()

{

    scanf("%d%d%d",&n,&s,&f);

    for(i=0;i<n;i++)

        for(j=0;j<n;j++) {

            scanf("%d",&G[i][j]);

            if(G[i][j]==-1)

                G[i][j]=INF;

        }


    dijkstra(s-1);

    if(d[f-1]!=INF)

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

    else

        printf("-1\n");



    return 0;

}


int min(int a,int b){return a<b?a:b;}

void dijkstra(int source)
{

    int i,j;

    for(i=0;i<n;i++){

        d[i]=G[source][i];

        used[i]=false;

    }

 

    d[source]=0;

    used[source]=true;



    int mn,ind_mn;

    for(i=0;i<n-1;i++){

        mn=INF;

        ind_mn=0;

        for(j=0;j<n;j++)

            if(!used[j]&&d[j]<mn){

                mn=d[j];

                ind_mn=j;
            }

        for(j=0;j<n;j++){

            if(!used[j])    
                d[j]=min(d[j],d[ind_mn]+G[ind_mn][j]);

        }
        used[ind_mn]=true;
    }
}