Воскресенье
24-09-2017
12:26
Главная страница
Каталог статей
Информист Приветствую Вас Гость | RSS
Регистрация
Вход
Меню сайта

Категории каталога
Delphi [3]
C++ [5]
Java [28]
программирование на Java
Assembler [4]
Алгоритмы на ассме
C# [1]
Eclipse [1]

Наш опрос
Что Вы веберете
Всего ответов: 206

Копилка
Если вам понравился наш сайт или вы нашли полезную информацию, то у вас есть возможность отблагодарить администрацию.

Начало » Статьи » Programming » C++

Алгоритм Дейкстры
В Википедии этот алгоритм замечательно расписан, даже с картинками, здесь же, я приведу код программы на языке C++, думаю, что разобраться в коде и реализовать его на нужном вам языке не составит большого труда.  

/* 
 * File:   main.cpp
 * Author: Alex Judge
 *
 * Created on 25 Февраль 2011 г., 0:51
 */

#include <stdlib.h>
#include <math.h>
#include <iosfwd>
#include <limits.h>

const int N = 6;

/*  * Реализация алгоритма Дейкстры.  * Находит кратчайшее расстояние от одной из вершин графа до всех остальных.  */ int main() {     int predok[N], nach = 0, D[N];     bool flag[N];     /* Пример графа взят из Википедии, в качестве наглядного примера      * http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры      */     int A[N][N] = {         {0, 7, 9, 14, INT16_MAX, INT16_MAX},         {7, 0, 10, INT16_MAX, INT16_MAX, 15},         {9, 10, 0, 2, INT16_MAX, 11},         {14, INT16_MAX, 2, 0, 9, INT16_MAX},         {INT16_MAX, INT16_MAX, INT16_MAX, 9, 0, 6},         {INT16_MAX, 15, 11, INT16_MAX, 6, 0}     };     for (int i = 0; i < N; i++) {         predok[i] = nach;         flag[i] = false;         D[i] = A[nach][i];     }     /* Пока известно только одно расстояние:      * от вершины nach  до нее же, равное 0.      */     flag[nach] = true;     predok[nach] = 0;     for (int i = 0; i < N - 1; i++) {         int k = 0;         int minras = INT16_MAX;         // Находим минимальное расстояние до непомеченных вершин         for (int j = 0; j < N; j++) {             if (!flag[j] && minras > D[j]) {                 minras = D[j];                 k = j;             }         }         // Вершина k помечается просмотренной         flag[k] = true;         for (int j = 0; j < N; j++) {             /* Если для вершины j еще не найдено кратчайшее расстояние от              * нач. и из вершины k по дуге A[k][j] путь в j короче              * чем найденное ранее, то запоминаем его.              */             if (!flag[j] && D[j] > D[k] + A[k][j]) {                 D[j] = D[k] + A[k][j];                 predok[j] = k;             }         }     }     puts("Rasstoyaniya:");     for (int i = 0; i < N; i++) {         printf("Ot %d do %d: %d\n", nach, i, D[i]);     }     puts("");     puts("IIYTb:");     /*      * Выводим путь задом на перед:      * в каждой ячейке массива predok хранится      * номер предыдущей ячейки - вершины кратчайшего пути.      * Например, предыдущая вершина для вершины 5 = predok[5]      */     for (int i = N; i > nach + 1; i--) {         printf("Ot %d do %d: ", i - 1, nach);         for (int j = i - 1; j > nach;) {             printf("%d ", j);             j = predok[j];         }         printf("%d\n", nach);     }     return (EXIT_SUCCESS); }


Источник: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
Категория: C++ | Добавил: Judge (08-11-2006) | Автор: AlexJudge
Просмотров: 16720 | Рейтинг: 3.6 |

Всего комментариев: 0
Имя *:
Email *:
Код *:
Форма входа

Поиск по каталогу
Яндекс


Поиск по Информисту

Наша кнопка


Друзья сайта

Статистика


Copyright MyCorp © 2006Сайт создан в системе uCoz