Кто-нибудь выложите пожалуйста простейшую реализацию алгоритма Дейкстры для нахождения кратчайшего расстояния между одной вершиной и всеми остальными в ориентированном взвешенном графе, где веса всех рёбер положительны. Простейшая в смысле та, что всегда выполняется за O(n^2) , моя реализация отчаянно не хочет работать Заранее спасибо
Здравствуйте, Аноним, Вы писали:
А>Кто-нибудь выложите пожалуйста простейшую реализацию алгоритма Дейкстры для нахождения кратчайшего расстояния между одной вершиной и всеми остальными в ориентированном взвешенном графе, где веса всех рёбер положительны. Простейшая в смысле та, что всегда выполняется за O(n^2) , моя реализация отчаянно не хочет работать Заранее спасибо
Здравствуйте, Аноним, Вы писали:
А>Кто-нибудь выложите пожалуйста простейшую реализацию алгоритма Дейкстры для нахождения кратчайшего расстояния между одной вершиной и всеми остальными в ориентированном взвешенном графе, где веса всех рёбер положительны. Простейшая в смысле та, что всегда выполняется за O(n^2) , моя реализация отчаянно не хочет работать Заранее спасибо
У этой реализации только одно ограничение: работает на графах с числом вершин <= 100.
int RelaxArray[2][100];
void Relax(int Vertex)
{
for(int i = 0;i < n;++i)
{
//есть ребро из Vertex в i
if(JailMap[Vertex][i] < 1001)
{
if(RelaxArray[0][i] > RelaxArray[0][Vertex] + JailMap[Vertex][i])
{
RelaxArray[0][i] = RelaxArray[0][Vertex] + JailMap[Vertex][i];
RelaxArray[1][i] = Vertex;
}
}
}
}
//алгоритм Дейкстры, возвращает длину кратчайшего пути
int ShortestPathDijkstra(int Beg,int End)
{
std::fill(RelaxArray[0],RelaxArray[0] + 100,2000000);
std::fill(RelaxArray[1],RelaxArray[1] + 100,-1);
RelaxArray[0][Beg] = 0;
RelaxArray[1][Beg] = -1;
bool Founded[100];
memset(Founded,0,100*sizeof(bool));
for(int i = Beg;i != End;)
{
Relax(i);
int Min = 2000000;
//элемент с минимальным значением релаксации
for(int j = 0;j < n;++j)
{
//до элемента еще не найден кратчайший путь
if(!Founded[j])
{
if(Min > RelaxArray[0][j])
{
Min = RelaxArray[0][j];
i = j;
}
}
}
Founded[i] = true;
}
return RelaxArray[0][End];
}
Re[2]: Простейшая реализация алгоритма Дейкстры на С
От:
Аноним
Дата:
08.01.06 23:42
Оценка:
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, Аноним, Вы писали:
А>>Кто-нибудь выложите пожалуйста простейшую реализацию алгоритма Дейкстры для нахождения кратчайшего расстояния между одной вершиной и всеми остальными в ориентированном взвешенном графе, где веса всех рёбер положительны. Простейшая в смысле та, что всегда выполняется за O(n^2) , моя реализация отчаянно не хочет работать Заранее спасибо SL>У этой реализации только одно ограничение: работает на графах с числом вершин <= 100. SL>
int RelaxArray[2][100];
SL>void Relax(int Vertex)
SL>{
SL> for(int i = 0;i < n;++i)
SL> {
SL> //есть ребро из Vertex в i
SL> if(JailMap[Vertex][i] < 1001)
SL> {
SL> if(RelaxArray[0][i] > RelaxArray[0][Vertex] + JailMap[Vertex][i])
SL> {
SL> RelaxArray[0][i] = RelaxArray[0][Vertex] + JailMap[Vertex][i];
SL> RelaxArray[1][i] = Vertex;
SL> }
SL> }
SL> }
SL>}
SL>//алгоритм Дейкстры, возвращает длину кратчайшего пути
SL>int ShortestPathDijkstra(int Beg,int End)
SL>{
SL> std::fill(RelaxArray[0],RelaxArray[0] + 100,2000000);
SL> std::fill(RelaxArray[1],RelaxArray[1] + 100,-1);
SL> RelaxArray[0][Beg] = 0;
SL> RelaxArray[1][Beg] = -1;
SL> bool Founded[100];
SL> memset(Founded,0,100*sizeof(bool));
SL> for(int i = Beg;i != End;)
SL> {
SL> Relax(i);
SL> int Min = 2000000;
SL> //элемент с минимальным значением релаксации
SL> for(int j = 0;j < n;++j)
SL> {
SL> //до элемента еще не найден кратчайший путь
SL> if(!Founded[j])
SL> {
SL> if(Min > RelaxArray[0][j])
SL> {
SL> Min = RelaxArray[0][j];
SL> i = j;
SL> }
SL> }
SL> }
SL> Founded[i] = true;
SL> }
SL> return RelaxArray[0][End];
SL>}
SL>
спасибо, было бы интересно увидеть ещё чью-нибудь реализацию
Re[2]: Простейшая реализация алгоритма Дейкстры на С
От:
Аноним
Дата:
15.01.06 16:46
Оценка:
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, Аноним, Вы писали:
А>>Кто-нибудь выложите пожалуйста простейшую реализацию алгоритма Дейкстры для нахождения кратчайшего расстояния между одной вершиной и всеми остальными в ориентированном взвешенном графе, где веса всех рёбер положительны. Простейшая в смысле та, что всегда выполняется за O(n^2) , моя реализация отчаянно не хочет работать Заранее спасибо SL>У этой реализации только одно ограничение: работает на графах с числом вершин <= 100. SL>
int RelaxArray[2][100];
SL>void Relax(int Vertex)
SL>{
SL> for(int i = 0;i < n;++i)
SL> {
SL> //есть ребро из Vertex в i
SL> if(JailMap[Vertex][i] < 1001)
SL> {
SL> if(RelaxArray[0][i] > RelaxArray[0][Vertex] + JailMap[Vertex][i])
SL> {
SL> RelaxArray[0][i] = RelaxArray[0][Vertex] + JailMap[Vertex][i];
SL> RelaxArray[1][i] = Vertex;
SL> }
SL> }
SL> }
SL>}
SL>//алгоритм Дейкстры, возвращает длину кратчайшего пути
SL>int ShortestPathDijkstra(int Beg,int End)
SL>{
SL> std::fill(RelaxArray[0],RelaxArray[0] + 100,2000000);
SL> std::fill(RelaxArray[1],RelaxArray[1] + 100,-1);
SL> RelaxArray[0][Beg] = 0;
SL> RelaxArray[1][Beg] = -1;
SL> bool Founded[100];
SL> memset(Founded,0,100*sizeof(bool));
SL> for(int i = Beg;i != End;)
SL> {
SL> Relax(i);
SL> int Min = 2000000;
SL> //элемент с минимальным значением релаксации
SL> for(int j = 0;j < n;++j)
SL> {
SL> //до элемента еще не найден кратчайший путь
SL> if(!Founded[j])
SL> {
SL> if(Min > RelaxArray[0][j])
SL> {
SL> Min = RelaxArray[0][j];
SL> i = j;
SL> }
SL> }
SL> }
SL> Founded[i] = true;
SL> }
SL> return RelaxArray[0][End];
SL>}
SL>
Здравствуйте, нельзя ли как-нибудь изменить этот алгоритм, чтобы он работал хотя бы для 1000 узлов? Или для этого придётся менять его суть?
Здравствуйте, <Аноним>, Вы писали:
А>Кто-нибудь выложите пожалуйста простейшую реализацию алгоритма Дейкстры для нахождения кратчайшего расстояния между одной вершиной и всеми остальными в ориентированном взвешенном графе, где веса всех рёбер положительны. Простейшая в смысле та, что всегда выполняется за O(n^2) , моя реализация отчаянно не хочет работать Заранее спасибо
Лови! Исходник на C++, ты уж извини, так привычней. Если что, переделать на C — не проблема.
/**************Описание графа*****************/const int N = 1000; // количество вершин
// матрица смежности: adj_matrix[i][j] == true,
// если между вершинами i и j существует реброbool adj_matrix[N][N];
int cost [N][N]; // веса рёбер
/*********************************************/
/*********Результаты работы алгоритма*********/int dist [N]; // расстояния от заданной вершиныint parent[N]; // из какой вершины пришли;
// служит для восстановления маршрута
/*********************************************/
// start -- вершина, от которой считаем расстоянияvoid dijkstra(int start)
{
// in_tree[i] == true, если для вершины i
// уже посчитано минимальное расстояниеbool in_tree[N] = {false};
for(int i = 0; i < N; i++)
dist[i] = INT_MAX; // машинная бесконечность,
// т. е. любое расстояние будет меньше данного
dist[start] = 0; // понятно почему, не так ли? ;)int cur = start; // вершина, с которой работаем
// пока есть необработанная вершинаwhile(!in_tree[cur])
{
in_tree[cur] = true;
for(int i = 0; i < N; i++)
{
// если между cur и i есть реброif(adj_matrix[cur][i])
{
// считаем расстояние до вершины i:
// расстояние до cur + вес ребраint d = dist[cur] + cost[cur][i];
// если оно меньше, чем уже записанноеif(d < dist[i])
{
dist[i] = d; // обновляем его
parent[i] = cur; // и "родителя"
}
}
}
// ищем нерассмотренную вершину
// с минимальным расстояниемint min_dist = INT_MAX;
for(int i = 0; i < N; i++)
{
if(!in_tree[i] && dist[i] < min_dist)
{
cur = i;
min_dist = dist[i];
}
}
}
// Теперь:
// в dist[i] минимальное расстояние от start до i
// в parent[i] вершина, из которой лежит оптимальный путь в i
}
Ремарки:
Алгоритм Дейкстры не подходит для графов с отрицательными весами
Вместо матрицы смежности можно использовать списки смежности
Чтобы не искать каждый раз вершину с минимальным расстоянием, можно использовать очередь по приоритету
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[2]: Простейшая реализация алгоритма Дейкстры на С
От:
Аноним
Дата:
16.01.06 15:48
Оценка:
Здравствуйте, Olegator, Вы писали:
O>Здравствуйте, <Аноним>, Вы писали:
А>>Кто-нибудь выложите пожалуйста простейшую реализацию алгоритма Дейкстры для нахождения кратчайшего расстояния между одной вершиной и всеми остальными в ориентированном взвешенном графе, где веса всех рёбер положительны. Простейшая в смысле та, что всегда выполняется за O(n^2) , моя реализация отчаянно не хочет работать Заранее спасибо
O>Лови! Исходник на C++, ты уж извини, так привычней. Если что, переделать на C — не проблема.
O>
O>/**************Описание графа*****************/
O>const int N = 1000; // количество вершин
O>// матрица смежности: adj_matrix[i][j] == true,
O>// если между вершинами i и j существует ребро
O>bool adj_matrix[N][N];
O>int cost [N][N]; // веса рёбер
O>/*********************************************/
O>/*********Результаты работы алгоритма*********/
O>int dist [N]; // расстояния от заданной вершины
O>int parent[N]; // из какой вершины пришли;
O> // служит для восстановления маршрута
O>/*********************************************/
O>// start -- вершина, от которой считаем расстояния
O>void dijkstra(int start)
O>{
O> // in_tree[i] == true, если для вершины i
O> // уже посчитано минимальное расстояние
O> bool in_tree[N] = {false};
O> for(int i = 0; i < N; i++)
O> dist[i] = INT_MAX; // машинная бесконечность,
O> // т. е. любое расстояние будет меньше данного
O> dist[start] = 0; // понятно почему, не так ли? ;)
O> int cur = start; // вершина, с которой работаем
O> // пока есть необработанная вершина
O> while(!in_tree[cur])
O> {
O> in_tree[cur] = true;
O> for(int i = 0; i < N; i++)
O> {
O> // если между cur и i есть ребро
O> if(adj_matrix[cur][i])
O> {
O> // считаем расстояние до вершины i:
O> // расстояние до cur + вес ребра
O> int d = dist[cur] + cost[cur][i];
O> // если оно меньше, чем уже записанное
O> if(d < dist[i])
O> {
O> dist[i] = d; // обновляем его
O> parent[i] = cur; // и "родителя"
O> }
O> }
O> }
O> // ищем нерассмотренную вершину
O> // с минимальным расстоянием
O> int min_dist = INT_MAX;
O> for(int i = 0; i < N; i++)
O> {
O> if(!in_tree[i] && dist[i] < min_dist)
O> {
O> cur = i;
O> min_dist = dist[i];
O> }
O> }
O> }
O> // Теперь:
O> // в dist[i] минимальное расстояние от start до i
O> // в parent[i] вершина, из которой лежит оптимальный путь в i
O>}
O>
O>Ремарки: O>
O>Алгоритм Дейкстры не подходит для графов с отрицательными весами O>Вместо матрицы смежности можно использовать списки смежности O>Чтобы не искать каждый раз вершину с минимальным расстоянием, можно использовать очередь по приоритету O>
Спасибо, мне на c++ и нужно. Очень хороший исходник))) Разобраться легко, не то что на некоторых сайтах... Нигде нормального не было.
Re[3]: Простейшая реализация алгоритма Дейкстры на С
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, нельзя ли как-нибудь изменить этот алгоритм, чтобы он работал хотя бы для 1000 узлов? Или для этого придётся менять его суть?
/* в данном алгоритме +00 == 0xffffffff == max(int) */#define VertexNum 100
#include <algorithm>
#define min(x,y) ((x < y)?(x):(y))
int JailMap[VertexNum][VertexNum];
int RelaxArray[2][VertexNum];
void Relax(int Vertex)
{
for(int i = 0;i < VertexNum;++i)
{
//есть ребро из Vertex в iif(JailMap[Vertex][i] < 0xffffffff)
{
if(RelaxArray[0][i] > RelaxArray[0][Vertex] + JailMap[Vertex][i])
{
RelaxArray[0][i] = RelaxArray[0][Vertex] + JailMap[Vertex][i];
RelaxArray[1][i] = Vertex;
}
}
}
}
//алгоритм Дейкстрыint ShortestPathDijkstra(int Beg,int End)
{
std::fill(RelaxArray[0],RelaxArray[0] + 100,2000000);
std::fill(RelaxArray[1],RelaxArray[1] + 100,-1);
RelaxArray[0][Beg] = 0;
RelaxArray[1][Beg] = -1;
bool Founded[100];
memset(Founded,0,100*sizeof(bool));
for(int i = Beg;i != End;)
{
Relax(i);
int Min = 2000000;
//элемент с минимальным значением релаксацииfor(int j = 0;j < VertexNum;++j)
{
//до элемента еще не найден кратчайший путьif(!Founded[j])
{
if(Min > RelaxArray[0][j])
{
Min = RelaxArray[0][j];
i = j;
}
}
}
Founded[i] = true;
}
return RelaxArray[0][End];
}
Заранее спасибо
