Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
vetalxxx
1 / 1 / 3
Регистрация: 22.11.2009
Сообщений: 55
1

Алгоритмы на графах

14.02.2010, 14:23. Просмотров 1458. Ответов 1
Метки нет (Все метки)

Привет всем, мне нужна помощь з алгоритмами на графах
нашел алгоритм Дейсктры
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// oo.cpp : Defines the entry point for the console application.
//
 
#include <stdafx.h>
#include <iostream>:
 
using namespace std;
 #include <conio.h>
#include <stdio.h>
#include <string>
 
 
//---------------------------------------------------------------------------
//Алгоритм Дейкстры.поиска кратчайшего пути
//#include <vcl.h>
 
 
#pragma hdrstop
#pragma argsused
 
#define VERTEXES 6  //Число вершин в графе
 
int v;
int main(int argc, char* argv[])
{
    setlocale( LC_ALL,"Russian" );
 
  // clrscr();
  
 
   int infinity=1000;                     // Бесконечность
   int p= VERTEXES;             // Количество вершин в графе
   int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
                                 0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };
 
   // Будем искать путь из вершины s в вершину g
   int s;                   // Номер исходной вершины
   int g;                   // Номер конечной вершины
   cout<<"Введите s: ";     // Номер может изменяться от 0 до p-1
   cin>>s;
   cout<<"Введите g: ";
   cin>>g;
   int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i
   int h[VERTEXES];  //h[i] - вершина, предшествующая i-й вершине
                 // на кратчайшем пути
 
   // Инициализируем начальные значения массивов
   int u;           // Счетчик вершин
   for (u=0;u<p;u++)
   {
      t[u]=infinity; //Сначала все кратчайшие пути из s в i 
    //равны бесконечности
      x[u]=0;        // и нет кратчайшего пути ни для одной вершины
   }
   h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   t[s]=0; // Кратчайший путь из s в s равен 0
   x[s]=1; // Для вершины s найден кратчайший путь
   v=s;    // Делаем s текущей вершиной
   
   while(1)
   {
      // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(a[v][u]==0)continue; // Вершины u и v несмежные
         if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не 
    //найден кратчайший путь
                // и новый путь в u короче чем 
    //старый, то
         {
            t[u]=t[v]+a[v][u];  //запоминаем более короткую длину пути в
    //массив t и
            h[u]=v; //запоминаем, что v->u часть кратчайшего 
    //пути из s->u
         }
      }
 
      // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;  // Для поиска самого короткого пути
      v=-1;            // В конце поиска v - вершина, в которую будет 
                       // найден новый кратчайший путь. Она станет 
                       // текущей вершиной
      for(u=0;u<p;u++) // Перебираем все вершины.
      {
         if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший 
                               // путь и если длина пути в вершину u меньше
                               // уже найденной, то
         {
            v=u; // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
      if(v==-1)
      {
         cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
         break;
      }
      if(v==g) // Найден кратчайший путь,
      {        // выводим его
         cout<<"Кратчайший путь из вершины "<<s<<" в вершину "<<g<<":";
       u=g;
       while(u!=s)
         {
            cout<<" "<<u;
            u=h[u];
         }
         cout<<" "<<s<<". Длина пути - "<<t[g];
       break;
      }
      x[v]=1;
   }
   getch();
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит 
 
Нет пути из вершины 3 в вершину 6. 
 
После ввода s = 0, q = 2 программа выводит 
 
Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/
 
//---------------------------------------------------------------------------
Нужно еще алгоритм Беллмана-Форда и другие, в нете полно исходников но я не могу слипить из них одну программу
матрица смежности такая как в Алгоритме Дейсктры


Например:
http://img4.immage.de/1402dadd3.png
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.02.2010, 14:23
Ответы с готовыми решениями:

Алгоритмы на графах
Поиск минимального остовного дерева как-то связан с поиском кратчайших путей между вершинами ?

Алгоритмы на графах, формирование двудольного неориентированного графа
Пишу на c#, у нас есть множество вершин графа, хранящихся в List&lt;V&gt; Множество ребер хранится в...

ГА на графах
Здравствуйте. Не могу разобраться как решать эту задачу. Используйте генетический алгоритм (для...

Предки в графах
Задача на определение, является ли вершина предком другой Условие: Определить для двух вершин...

Алгоритм А* на графах
Стоит задача разработать функцию поиска пути в неориентированном графе методом А*. Проблема: как на...

1
vetalxxx
1 / 1 / 3
Регистрация: 22.11.2009
Сообщений: 55
15.02.2010, 22:49  [ТС] 2
может есть у кого исходник программы з алгоритмом Беллмана-Форда

Добавлено через 3 часа 26 минут
Привет всем, вот нашел функцию Алгоритм Форда-Беллмана
на сайте
http://hardfire.far.ru/index.php?id=ford_bellman.htm
========================================================
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ford_bellman (int x, vector < vector < int > > &D, 
                        vector < int > &w, vector < int > &p)
{
    int i, j, k;
    int n = D.size ();
    w.assign (n, 0);
    p.assign (n, - 1);
    for (i = 0; i < n; ++ i)
        w[i] = D[x][i];
    w[x] = 0;
    
    for (k = 0; k < n; ++ k)
        for (i = 0; i < n; ++ i)
            for (j = 0; j < n; ++ j)
                if (w[i] > w[j] + D[j][i])
                {
                    w[i] = w[j] + D[j][i];
                    p[i] = j;
                }
}
========================================================
Помогите пожалуйста, я не могу разобраться, у меня есть матрица
0,1,0,0,1,3,
1,0,5,0,0,1,
0,5,0,5,20,1,
0,0,5,0,3,2,
1,0,20,3,0,10,
3,1,1,2,10,0

ка посчитать в этом графе кратчайший путь от одной вершины к второй
функция требует
C++
1
ford_bellman(int x, vector < vector < int > > &R, int n,vector < int > &w, vector < int > &p)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.02.2010, 22:49

Список смежности во взвешенных графах
Здрасте! Не получается реализовать списки смежности для ВЗВЕШЕННОГО графа. Я умею...

Двунаправленный поиск кратчайшего пути в графах
Никто не встречал реализованный на c\c++ алгоритм? Добавлено через 17 часов 24 минуты помогите...

Порядок сборки программного комплекса на графах
Ребят, помогите пожалуйста понять смысл курсовой по &quot;алгоритмам и структурам данных&quot;. Учусь на 2...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru