Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/14: Рейтинг темы: голосов - 14, средняя оценка - 5.00
Adina
14 / 14 / 5
Регистрация: 06.04.2012
Сообщений: 287
1

Создать простой граф используя алогоритм Дейкстры

21.04.2012, 05:09. Просмотров 2638. Ответов 5
Метки нет (Все метки)

В Windows Forms создать простой граф используя алогоритм Дейкстры. Искала в интернете - находила. Но все трудно для меня, ни как не пойму. Пожалуйста, может ли вы в Windows Forms создать простой пример графа используя алгоритм дейктры. Очень нужно разобраться.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2012, 05:09
Ответы с готовыми решениями:

Построить граф, определить кратчайший путь алгоритмом Дейкстры
В задании требуется по матрице весов построить граф (см ниже) дальше определить кратчайший путь по...

Определить кратчайший маршрут в графе, используя алгоритм Дейкстры.
Разработать и реализовать в виде программы алгоритм Дейкстры для графа заданного матрицей весовых...

Доказать, что любой граф на n вершинах с n ребрами содержит простой цикл
Помогите, пожалуйста, решить задачу по теории графов. Нужно доказать, что любой граф на n вершинах...

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка...

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности
Нужно задать граф списком ребер и вывести его в виде матрицы смежности. Знаю что в i строке j...

5
ValeryLaptev
Эксперт С++
1055 / 834 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
21.04.2012, 05:52 2
Алгоритм Дейкстры - это поиск наименьшего пути на графе.
Граф сначала создается, потом отображается на форме. А потом уж ищется путь с помощью алгоритма Дейкстры.
Если сложно - поищите другую профессию, еще не поздно...
0
Adina
14 / 14 / 5
Регистрация: 06.04.2012
Сообщений: 287
21.04.2012, 10:19  [ТС] 3
ValeryLaptev, Спасибо, но я теории про графах начиталась. Мне нужно больше практики, больше показательного кода, чтобы я поняла . + обычными способами создания, без Linq и т.п.

Добавлено через 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
 class Program
  {
 
     public static int[,] a = new int[9, 9]
     {{   0,   3,1000,   4,1000,1000,1000,1000,1000},
      {   3,   0,   4,1000,1000,1000,1000,   7,1000},
      {1000,   4,   0,   5,   2,   4,   4,   6,   9},
      {   4,1000,   5,   0,   6,1000,1000,1000,1000},
      {1000,1000,   2,   6,   0,   5,1000,1000,1000},
      {1000,1000,   4,1000,   5,   0,   3,1000,   4},
      {1000,1000,   4,1000,1000,   3,   0,1000,   4},
      {1000,   7,   6,1000,1000,1000,1000,   0,   8},
      {1000,1000,   9,1000,1000,   4,   4,   8,   0}};
     public static int[] d = new int[10];
     public static int[] post = new int[10];
     public static bool[] t = new bool[10];
     public static int i, j, p, k, minras;
 
     public static void poisk()
     {
        //начальные установк
        minras = 0;
        for (i = 0; i < 9; i++)
        {
            post[i] = 0;
            t[i] = true;
            d[i] = a[0,i];
        }
        t[0] = false;
        post[0] = 0;
 
        for (i = 0; i < 8; i++)
        {
            // поиск вершины k
            minras = 1000;
            for (j = 0; j < 9; j++)
                if ((t[j] == true) && (minras > d[j]))
                {
                    minras = d[j]; k = j;
                }
            // поиск маршрутов и минимальных расстояний через вершину k
            t[k] = false;
            for (j = 0; j < 9; j++)
                if ((t[j] == true) && (d[j] > d[k] + a[k,j]))
                {
                    d[j] = d[k] + a[k,j];
                    post[j] = k;
                }
        }
     }
 
     public static void print()
     {
        // печать матрицы смежности
        Console.WriteLine("Печатаем матрицу смежности : ");
        for (i = 0; i < 9; i++)
        {
            for (j = 0; j < 9; j++)
                Console.Write("\t" + a[i, j]);
            Console.WriteLine();
        }
        Console.WriteLine();      
        
        // печать массива минимальных расстояний
        for (i = 0; i < 9; i++) Console.Write("\t" + i);
        Console.WriteLine();
 
        for (i = 0; i < 9; i++) Console.Write("\t" + d[i]);
        Console.WriteLine();
        
        // печать массива маршрутов
        for (i = 0; i < 9; i++) Console.Write("\t" + post[i]);
        Console.WriteLine(); 
        
        // печать маршрута от 0 вершины графа до его 8 вершины
        p = 8;
        Console.Write("Конечная вершина = 8 ");
        
        do
        {
            p = post[p];
            Console.Write("\t" + p);
        }
        while (p != 0);
        Console.WriteLine(" Начальная вершина = 0 "); 
     }
 
    static void Main(string[] args)
      {
 
          poisk();
          print();
          Console.ReadLine();
    }
  }
}
Добавлено через 52 секунды
Что такое minras ? )))
0
ValeryLaptev
Эксперт С++
1055 / 834 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
21.04.2012, 16:27 4
Цитата Сообщение от Adina Посмотреть сообщение
Что такое minras ? )))
Очевидно, минимальное расстояние...
0
Adina
14 / 14 / 5
Регистрация: 06.04.2012
Сообщений: 287
22.04.2012, 13:21  [ТС] 5
Как вот его теперь применять на форме ?
0
ValeryLaptev
Эксперт С++
1055 / 834 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
24.04.2012, 21:10 6
Цитата Сообщение от Adina Посмотреть сообщение
Как вот его теперь применять на форме ?
Его можно только вывести как результат.
Подробности можете спросить либо в форуме по Додиезу, либо у CLIшников - судя по вашему тексту.
Там сначала форму надо создать. Что на ней нарисуете, то и будет. А потом связать форму и события в программе. И обработчики событий написать.
0
24.04.2012, 21:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2012, 21:10

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности
Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы...

Алогоритм построения изображения
Мы с другом вчера заключили пари: у кого алгоритм построения изображения будет хуже, тот и...

Нарисовать рамку из звездочек используя модуль граф
Нарисовать рамку из звездочек используя модуль граф.


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

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

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