REFERATUA.ORG.UA — База українських рефератів



Головна Математика, Геометрія → Алгоритм Дейкстра

позначених на кроці (3) ребер (дуг) (можна довести, що він існує й единий); ВИХІД("рішення знайдене");

  • інакше переходимо на крок (1).

    Алгоритм можна модифікувати так, щоб він закінчував роботу після одержання усіма вершинами графа G постійних міток, тобто знаходяться найкоротші шляхи з s в усі вершини графа. Алгоритм визначить основне дерево D найкоротших шляхів з вершини s. Для будь-якої вершини v єдиний (s,v) - шлях у дереві D буде найкоротшим (s,v) - шляхом у графі G.

    Алгоритм Дейкстра не завжди знаходить правильне рішення у випадку довільних ваг ребер (дуг) графа. Наприклад, для орграфа, зображеного на малюнку, алгоритм Дейкстра знайде маршрут s(s,t)t довжини 1 між вершинами s і t, а не мінімальний маршрут довжини 2+(-2)=0, що проходить через третю вершину графа.

    Алгоритм  Дейкстра
    Приклад орграфа, для якого не будем застосовувати алгоритм Дейкста.

    Текст програми написаної на основі алгоритму Дейкстра

    /* Алгоритм пошуку дерева найкоротших шляхів у зваженому графі */

    /* Е.Дейкстра 1959 р. */

    #include

    #include

    #include

    int load_matrix(int n, double* weigh); /* Уведення матриці ваг */

    int deik(int n, int s, double* weigh, int* Q, double* L); /* Алгоритм пошуку */

    void print(int n, int* Q, double* L); /* Висновок результату */

    void main(void){

    int n=0,s=0,ret=0;

    double *weigh;

    int* Q; /* Масив міток покажчиків на попередню вершину */

    double* L; /* Масив найдених ваг шляху до вершини */

    printf("nАлгоpитм пошуку дерева найкоротших шляхів у зваженому графі.n");

    printf("Е.Дейкстpа, 1959 р.n");

    printf("nВведіть кількість вершин..");

    scanf("%d",&n);

    if (n <= 1){

    printf("nКількість вершин повинне бути більше одиниці!n");

    exit(1);

    }

    printf("nВведіть початкову вершину..");

    scanf("%d",&s);

    s--;

    if ((s < 0)||(s > (n-1))){

    printf("nПочаткова вершина зазначена неправильно! n");

    exit(1);

    }

    Q=malloc(n*sizeof(int));

    L=malloc(n*sizeof(double));

    weigh=malloc(sizeof(double)*n*n);

    if ((weigh == NULL)||(Q == NULL)||(L == NULL)){

    printf("nHедостатньо пам'яті для завантаження масиву! n");

    exit(2);

    }

    ret=load_matrix(n,weigh);

    if (ret != 0){

    printf("nПомилка введення даних!n");

    exit(5);

    }

    ret=deik(n,s,weigh,Q,L);

    if (ret != 0){

    switch (ret){

    case 1 :

    printf("nГpаф не є зв'язаним!n");

    exit(3);

    case 2 :

    printf("nHедостаточно пам'яті для роботи!n");

    exit(4);

    }

    }

    print(n,Q,L);

    free(weigh);

    free(Q);

    free(L);

    }

    int load_matrix(int n, double* weigh){

    int i,j,k;

    double tmp;

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

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

    weigh[n*i+j]=(-1);

    }

    }

    printf("nВведіть послідовно ваги ребер для зазначених чи вершин -1 для несуміжних.");

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

    for (j=i+1; j < n; j++){

    printf("nВеpшини %d і %d ",i+1,j+1);

    k=scanf("%lf",&tmp);

    if (k != 1){return(1);}

    weigh[i*n+j]=tmp;

    }

    }

    return(0);

    }

    int deik(int n,int s, double* weigh, int* Q, double* L){

    int i,j,k;

    int* QI; /* Масив індикаторів сталості міток покажчиків */

    double tmp;

    QI=calloc(n,sizeof(int));

    if (QI == NULL){return(2);}

    QI[s]=1;

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

    Q[i]=(-1);

    L[i]=DBL_MAX;

    }

    Q[s]=s;

    L[s]=0;

    weigh[n*(n-1)+s]=0;

    for (k=0; k < n; k++){ /* Основний цикл по вершинах */

    for (i=0; i < n; i++){ /* Цикл по рядках матриці ваг */

    for (j=i+1; j < n; j++){ /* Цикл по стовпцях матриці ваг */

    if ((QI[i]+QI[j] == 1)&&

    (QI[i]*QI[j] == 0)&&

    (weigh[i*n+j] != (-1.0))&&

    (((QI[i] == 1)&&((L[i]+weigh[i*n+j]) < L[j]))||

    ((QI[j] == 1)&&((L[j]+weigh[i*n+j]) < L[i])))){

    if (QI[i] == 1){

    L[j]=L[i]+weigh[i*n+j];

    Q[j]=i;

    }

    else{

    L[i]=L[j]+weigh[i*n+j];

    Q[i]=j;

    }

    }

    }

    }

    for (tmp=DBL_MAX,i=0; i < n; i++){

    if ((tmp > L[i])&&(QI[i] == 0)){

    tmp=L[i];

    j=i;

    }

    }

    QI[j]=1;

    }

    free(QI);

    return(0);

    }

    void print(int n, int* Q, double* L){

    int i;

    printf("nnДеpево найкоротших шляхів:");

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

    printf("nВеpшина: %d Предок: %d Вага: %5.2lf",i+1,Q[i]+1,L[i]);

    }

    }

    Результат виконання програми

    Алгоритм пошуку дерева найкоротших шляхів у зваженому графі.

    Е.Дейкстра, 1959 р.

    Уведіть кількість вершин.. 6

    Уведіть початкову вершину.. 6

    Уведіть послідовно ваги ребер для зазначених чи вершин -1 для несуміжних.

    Вершини 1 і 2 2

    Вершини 1 і 3 -1

    Вершини 1 і 4 2

    Вершини 1 і 5 -1

    Вершини 1 і 6 5

    Вершини 2 і 3 2

    Вершини 2 і 4 -1

    Вершини 2 і 5 2

    Вершини 2 і 6 -1

    Вершини 3 і 4 -1

    Вершини 3 і 5 -1

    Вершини 3 і 6 12

    Вершини 4 і 5 1

    Вершини 4 і 6 2

    Вершини 5 і 6 5

    Дерево найкоротших шляхів:

    Вершина: 1 Предок: 4 Вага: 4.00

    Вершина: 2 Предок: 5 Вага: 5.00

    Вершина: 3 Предок: 2 Вага: 7.00

    Вершина: 4 Предок: 6 Вага: 2.00

    Вершина: 5 Предок: 4 Вага: 3.00

    Вершина: 6 Предок: 6 Вага: 0.00

    Графічне зображення початкового графа та дерева мінімальних шляхів після виконання програми

    Тестовий зв'язний зважений для алгоритму пошуку дерева шляхів з вершини 6 (Е. Дейкстра 1959р.)

    Рішення: дерево найкоротших шляхів з вершини 6

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

    4.Висновок

    Ця курсова робота показує що дискретна математика, поряд з такими класичними розділами математики, як математичний аналіз, диференціальні рівняння, у навчальних планах спеціальності "Прикладна математика" і різні розділи по математичній логіці, алгебрі, комбінаториці і теорії графів тісно пов'язані із сучасним програмуванням. Причини цього неважко зрозуміти, просто розглянувши задачу, у цій курсовій роботі, яка за допомогою алгоритму Е. Дейкстра має змогу пошуку найкоротшого шляху в графі .

































    5.Література

  • Зыков А.А. Теорія кінцевих графів. - Новосибірськ: Наука, 1969.

  • Харари Ф. Теорія графів. - М.: Світ, 1973.

  • Зыков А.А. Основи теорії графів. - М.: Наука, 1987.

  • Кристофидес Н. Теорія графів. Алгоритмічний підхід. - М.: Світ, 1978.

  • Майника Э. Алгоритми оптимізації на мережах і графах. - М.: Світ, 1981.

  • Ловас Л., Пламмер М. Прикладні задачі теорії графів. Теорія паросочетаний у математику, фізику, хімії. - М.: Світ, 1998.


  •  
    Загрузка...