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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Андрейка
419 / 223 / 27
Регистрация: 25.03.2009
Сообщений: 744
#1

Нахождение кратчайшего пути от одной вершины графа до другой - C++

07.06.2009, 17:34. Просмотров 832. Ответов 4
Метки нет (Все метки)

Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей
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
#include <iostream.h>
#include <conio.h>
#include <math.h>
#define v 8
int main()
{
clrscr();
cout<<"vvedite i and j"<<endl;
int i,j,adj[v][v];
for (i=0;i<v;i++)
for (j=0;j<v;j++)
adj[i][j]=0;
for (i=0;i<v;i++)
adj[i][i]=0;
while (cin>>i>>j)
{
cout<<"vvedite i and j"<<endl;
adj[i][j]=1;adj[j][i]=1;
}
cout<<' '<<' ';
for (i=0;i<8;i++)
cout<<i<<' '<<' ';
cout<<endl;
for (i=0;i<v;i++)
{
for (j=0;j<v;j++)
cout<<' '<<' '<<adj[i][j];
cout<<endl;
}
getch();
return 0;
}
то есть верхняя строка это вершины графа дальше идём от этого значения вниз по столбцу смотрим если на пересечении стоит 1 то это вершина связана ребром с другой вершиной и так далее. Помогите найти кратчайший путь от одной вершины до другой.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.06.2009, 17:34     Нахождение кратчайшего пути от одной вершины графа до другой
Посмотрите здесь:

C++ Проверка графа на возможность достижимости одной вершины из другой
Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней C++
C++ Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
C++ Нахождение кратчайшего пути по матрице, или передвижение привидений в игре Пакмен
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
Нахождение пути от одной ячейки к другой в массиве C++
C++ Нахождение кратчайшего пути, поиск с возвратом
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа C++
C++ Нахождение кратчайшего пути
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А C++
Написать программу для нахождения кратчайшего пути между заданными вершинами графа C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
exe-dealer
301 / 154 / 4
Регистрация: 07.06.2009
Сообщений: 538
07.06.2009, 17:37     Нахождение кратчайшего пути от одной вершины графа до другой #2
гугли алгоритм дейкстры


могу на C# только показать, у меня работало
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
using System;
using System.Collections.Generic;
using System.IO;
 
namespace dijkstra
{
    public static class program
    {
        public static int input(ref StreamReader stream)
        {
            char next;
            do { next = (char)stream.Read(); } while (!(char.IsDigit(next) || next == '-'));
            string s = "";
            while (char.IsDigit(next) || next == '-') { s += next; next = (char)stream.Read(); }
            return int.Parse(s);
        }
 
        internal static void Main()
        {
            StreamReader fr = new StreamReader("input.txt");
            int n = Convert.ToInt32(fr.ReadLine());
            int[,] c = new int[n, n];
 
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    c[i, j] = input(ref fr);
                    if (c[i, j] == 0) { c[i, j] = int.MaxValue; }
                }
            }
            fr.Dispose();
 
            int s/*старт*/= 6 - 1, dest = 5 - 1;
 
            int[] d/*расстояние от начала до вершины*/ = new int[n], p/*предок*/ = new int[n];
            bool[] f = new bool[n];
 
            //инициализация
            for (int i = 0; i < n; i++) { p[i] = s; d[i] = c[s, i]; }
            f[s] = true;
            p[s] = -1;
 
            for (int i = 0; i < n - 1; i++)
            {
                /*находим среди непомеченых вершин ту, путь от 
                  корня в которую на данный момент минимальный*/
                int k = 0, mindist = int.MaxValue;
                for (int j = 0; j < n; j++) { if (!f[j] && mindist > d[j]) { mindist = d[j]; k = j; } }
 
                f[k] = true; /*помечаем эту вершину*/
 
                /*обновление кратчайших путей*/
                for (int j = 0; j < n; j++)
                {
                    if (c[k, j] == int.MaxValue) { continue; } //есть ли ребро k--j
                    int l = d[k] + c[k, j];
                    if (!f[j] && d[j] > l) { d[j] = l; p[j] = k; }
                }
            }
 
 
            int prev = dest; string path = "";
            for (; ; )
            {
                path = (prev + 1) + " " + path;
                if (prev == s) { break; }
                prev = p[prev];
            }
 
            Console.WriteLine(path + "\n" + d[dest]);
            Console.ReadLine();
        }
 
    }
 
}
Monte-Cristo
2787 / 1373 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
07.06.2009, 18:35     Нахождение кратчайшего пути от одной вершины графа до другой #3
ну у вас неконкретно поставлена задача... вам необходим кратчайший путь:
по стоимости или по кол-ву посещенных вершин...

Алгоритм Дейкстры: по стоимости..
Я писал его недавно на лабу.. он
тут

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
#include <iostream>
using namespace std;
 
#define N 100000
//---------------------------------------------------------------------------
bool Exist(int *V, int n, int x);
void Dejkstra(int **G, int n);
//---------------------------------------------------------------------------
int main()
{
   const int n=6;
   int G[n][n] = 
   {
       N,   7,   9,   N,   N,  14,
       7,   N,  10,  15,   N,   N,
       9,  10,   N,  11,   N,   2,
       N,  15,  11,   N,   6,   N,
       N,   N,   N,   6,   N,   9,
      14,   N,   2,   N,   9,   N
   };
   int **M = new int*[n];
   for (int i=0; i<n; i++) M[i] = G[i];
 
   Dejkstra(M, n);
 
   system("pause");
   return 0;
}
//---------------------------------------------------------------------------
bool Exist(int *V, int n, int x)
{
   for (int j=0; j<n; j++)
      if (V[j] == x) return true;
   return false;
}
//---------------------------------------------------------------------------
void Dejkstra(int **G, int n)
{
   int s;
   int *V = new int[n];
 
   for (int i=0; i<n; i++) V[i] = -1;
 
   cout << "Please, enter top of entry -> ";
   cin >> s;
 
   G[s][s] = 0;
 
   for (int j=0; j<n; j++)
   {
      int min;
      bool first = true;
      V[j] = s;
 
      for (int i=0; i<n; i++)
      {   
         if (G[s][i]!=-1 && Exist(V,n,i)==false)
         {
            if (first == true) { min = i; first = false; } 
            if (G[s][min]>G[s][i] && j!=n-1) min = i;
            if ((G[s][s]+G[s][i]) < G[i][i]) G[i][i] = G[s][s]+G[s][i];
         }
      }
 
      if (j!=n-1) 
         s = min;
   }
 
    cout << "\nRoad = ";
    for (int i=0; i<n; i++)
       cout << V[i] << " ";
    cout << "\n\n";
 
    for (int i=0; i<n; i++)
       cout << "from top " << V[0] << " to " << i << " = " << G[i][i] << endl;
    cout << endl;
 
    delete[] V;
}
//---------------------------------------------------------------------------
Андрейка
419 / 223 / 27
Регистрация: 25.03.2009
Сообщений: 744
07.06.2009, 19:35  [ТС]     Нахождение кратчайшего пути от одной вершины графа до другой #4
упс , мне в общем нужно построить путь с одной вершины до другой.так в условии)
exe-dealer
301 / 154 / 4
Регистрация: 07.06.2009
Сообщений: 538
07.06.2009, 20:00     Нахождение кратчайшего пути от одной вершины графа до другой #5
раз матрица смежности, то по колву вершин я так думаю, иначе была бы матрица весов. Но там имхо без разницы - можно заюзать дейкстру по стоимости, но вместо матрицы весов положить матрицу смежности, только нули заменить на машинную бесконечность.
Yandex
Объявления
07.06.2009, 20:00     Нахождение кратчайшего пути от одной вершины графа до другой
Ответ Создать тему
Опции темы

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