Форум программистов, компьютерный форум CyberForum.ru

Реализация алгоритма Дейкстры - C++

Восстановить пароль Регистрация
 
ArcangelJonni
0 / 0 / 0
Регистрация: 17.05.2013
Сообщений: 64
19.12.2013, 18:41     Реализация алгоритма Дейкстры #1
Кто может подсказать (или указать где найти) код алгоритма Дейкстры на С++?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2013, 18:41     Реализация алгоритма Дейкстры
Посмотрите здесь:

Выкладываю реализацию алгоритма Дейкстры на С++ C++
Реализация алгоритма C++
Реализация алгоритма RLE C++
Реализация алгоритма FOREL C++
Задача с использованием алгоритма Дейкстры C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ПерС
366 / 282 / 84
Регистрация: 05.11.2013
Сообщений: 806
Записей в блоге: 5
Завершенные тесты: 1
19.12.2013, 18:46     Реализация алгоритма Дейкстры #2
вот например
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include "stdafx.h"
#include <iostream>
using namespace std;
const int V=6;
//алгоритм Дейкстры
void Dijkstra(int GR[V][V], int st)
{
int distance[V], count, index, i, u, m=st+1;
bool visited[V];
for (i=0; i<V; i++)
{
distance[i]=INT_MAX; visited[i]=false;
}
distance[st]=0;
for (count=0; count<V-1; count++)
{
int min=INT_MAX;
for (i=0; i<V; i++)
if (!visited[i] && distance[i]<=min)
{
min=distance[i]; index=i;
}
u=index;
visited[u]=true;
for (i=0; i<V; i++)
if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&
distance[u]+GR[u][i]<distance[i])
distance[i]=distance[u]+GR[u][i];
}
cout<<"Стоимость пути из начальной вершины до остальных:\t\n";
for (i=0; i<V; i++) if (distance[i]!=INT_MAX)
cout<<m<<" > "<<i+1<<" = "<<distance[i]<<endl;
else cout<<m<<" > "<<i+1<<" = "<<"маршрут недоступен"<<endl;
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
int start, GR[V][V]={
{0, 1, 4, 0, 2, 0},
{0, 0, 0, 9, 0, 0},
{4, 0, 0, 7, 0, 0},
{0, 9, 7, 0, 0, 2},
{0, 0, 0, 0, 0, 8},
{0, 0, 0, 0, 0, 0}};
cout<<"Начальная вершина >> "; cin>>start;
Dijkstra(GR, start-1);
system("pause>>void");
}
Dinosuaur
0 / 0 / 0
Регистрация: 23.04.2014
Сообщений: 6
21.12.2014, 19:09     Реализация алгоритма Дейкстры #3
ПерС, я не много не понимаю условие:
C++
1
2
3
4
if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&
distance[u]+GR[u][i]<distance[i])
distance[i]=distance[u]+GR[u][i];
}
вы не могли бы пояснить? При переносе алгоритма на C# компилятор жалуется на строчку
C++
1
!visited[i] && GR[u][i]
не могу понять что она значит : Если вершина не посещена и ..?
ПерС
366 / 282 / 84
Регистрация: 05.11.2013
Сообщений: 806
Записей в блоге: 5
Завершенные тесты: 1
23.12.2014, 17:53     Реализация алгоритма Дейкстры #4
if (GR[u][i]) в си то же самое, что if (GR[u][i]!=0)
Yandex
Объявления
23.12.2014, 17:53     Реализация алгоритма Дейкстры
Ответ Создать тему
Опции темы

Текущее время: 14:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru