Алгоритм Дейкстры для большого количества точек

@Yukikaze · Регистрация: 12.12.2011

Студворк — интернет-сервис помощи студентам

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

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
re = new RouteEngine.RouteEngine();
            Location loc0 = new Location { Identifier = "leftBot" };
            Location loc1 = new Location { Identifier = "leftTop" };
            Location loc2 = new Location { Identifier = "rightTop" };
            Location loc3 = new Location { Identifier = "rightBot" };
 
            re.Locations.Add(loc0);
            re.Locations.Add(loc1);
            re.Locations.Add(loc2);
            re.Locations.Add(loc3);
 
            re.Connections.Add(new Connection(loc0, loc1, 4));
            re.Connections.Add(new Connection(loc1, loc2, 4));
            re.Connections.Add(new Connection(loc2, loc3, 4));
            re.Connections.Add(new Connection(loc3, loc0, 4));
            re.Connections.Add(new Connection(loc1, loc0, 4));
            re.Connections.Add(new Connection(loc2, loc1, 4));
            re.Connections.Add(new Connection(loc3, loc2, 4));
            re.Connections.Add(new Connection(loc0, loc3, 4));
 
            Dictionary<Location, Route> _shortestPaths = re.CalculateMinCost(loc0);
            var _shortestLocations = (List<Location>)(from s in _shortestPaths orderby s.Value.Cost select s.Key).ToList();
            
            foreach (var _location in _shortestLocations)
            {
                listBox1.Items.Add(_shortestPaths[_location]);
            }

В вышеприведенном коде описаны 4 точки соединенные между собой в квадрат, а что делать если количество точек не 4, а например 100 или больше, не заполнять же руками все соединения.

Как должен выглядеть алгоритм для вышеприведенной таблицы если точки соединяются только со смежными, то есть 1 - 2, 2 - 3, и вниз 1 - 11, 11 - 21 и т.д

@I2um1 · 04.02.2012, 11:26

Сообщение от Yukikaze

В вышеприведенном коде описаны 4 точки соединенные между собой в квадрат, а что делать если количество точек не 4, а например 100 или больше, не заполнять же руками все соединения.

Гениально, о словарях, списках, обходах коллекции я смотрю знакомы. Тогда нафига было делать это:

Сообщение от Yukikaze

C#
1
2
3
4
Location loc0 = new Location { Identifier = "leftBot" };
Location loc1 = new Location { Identifier = "leftTop" };
Location loc2 = new Location { Identifier = "rightTop" };
Location loc3 = new Location { Identifier = "rightBot" };

Массив слабо было сделать? Где в цикле добавить их. После чего в цикле построить и добавить все связи? И такие имена идентификаторам лучше не давать. Имхо, вообще это бесполезный функционал.

Кстати, если не очевиден смысл строки кода, то необходимо добавлять комментарий.

Сообщение от Yukikaze

C#
1
re.Connections.Add(new Connection(loc0, loc1, 4));

И в вашем случае не помешало бы еще создать конструктор с теми же параметрами и дополнительным bool-значением, который бы говорил двунаправленная ли это связь на графе. Но я почему-то уверен, что у вас это не получится сделать, наверняка что-то криво сделано, так как это мне выносит мозг:

Сообщение от Yukikaze

C#
1
re = new RouteEngine.RouteEngine();

Я конечно не уверен, но строку:

C#
1
var _shortestLocations = (List<Location>)(from s in _shortestPaths orderby s.Value.Cost select s.Key).ToList();

Можно написать как:

C#
1
var _shortestLocations = _shortestPaths.OrderBy(x => x.Value.Cost).Select(x => x.Key).ToList();

@Yukikaze · 04.02.2012, 11:49 **[ТС]**

Все что привел выше было для примера, как я должен был все заполнять в циклах, если я потерялся в алгоритме добавления связей?

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
void doIt(int Size)
        {
            re = new RouteEngine.RouteEngine();
            int[] arr0 = new int[Size];
            int[] arr10 = new int[Size];
 
            for (int i = 0; i < arr0.Length; i++)
            {
                arr0[i] = i;
                arr10[i] = i*10;
            }
            
            var allLocations = new List<Location>();
            List<Connection> allConection = new List<Connection>();
            for (int i = 0; i < 100; i++ )
            {
                allLocations.Add(new Location{Identifier = i.ToString()});
            }
 
            foreach (Location _loc in allLocations)
            {
                re.Locations.Add(_loc);
            }
 
            //Вниз
            foreach (int i in arr10)
            {
                foreach (int n in arr0)
                {
                    if (i + n != 9 && (i + n + 1) % 10 != 0)
                        allConection.Add(new Connection(allLocations[i + n],allLocations[i + n + 1], 4)); // (i + n) + "  " + ((i + n) + 1));
                }
            }
 
            //Вверх
            foreach (int i in arr10)
            {
                foreach (int n in arr0)
                {
                    if (i + n != 9 && (i + n + 1) % 10 != 0)
                        allConection.Add(new Connection(allLocations[i + n + 1], allLocations[i + n], 4)); // (i + n) + "  " + ((i + n) + 1));
                }
            }
 
            //Вправо
            foreach (int i in arr0)
            {
                foreach (int n in arr10)
                {
                    if ((i + n - 10) >= 0)
                        allConection.Add(new Connection(allLocations[i + n - 10], allLocations[i + n], 4)); //listBox1.Items.Add((i + n - 10) + "  " + (i + n));
                }
            }
 
            //Влево
            foreach (int i in arr0)
            {
                foreach (int n in arr10)
                {
                    if ((i + n - 10) >= 0)
                        allConection.Add(new Connection(allLocations[i + n], allLocations[i + n - 10], 4)); //listBox1.Items.Add((i + n - 10) + "  " + (i + n));
                }
            }
            re.Connections.AddRange(allConection);
            Dictionary<Location, Route> _shortestPaths = re.CalculateMinCost(allLocations[0]);
            var _shortestLocations = (List<Location>)(from s in _shortestPaths orderby s.Value.Cost select s.Key).ToList();
 
            foreach (var _location in _shortestLocations)
            {
                listBox1.Items.Add(_shortestPaths[_location]);
            }
        }

Как сделать связь по диагонали я так и не понял
ЗЫ

C#
1
re = new RouteEngine.RouteEngine();

создание нового экземпляра класса RouteEngine который находится в неймспейсе RouteEngine

@I2um1 · 04.02.2012, 12:24

Yukikaze, эх, копи-пастить не хорошо. Надо было это все сделать одной конструкцией. Вот набросок:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
int size = (int)Math.Sqrt(allLocations.Count);
for (int i = 0; i < size; i++)
    for (int j = 0; j < size - 1; j++)
    {
        // Вправо?
        //Console.WriteLine("{0} {1}", i * size + j, i * size + j + 1);
        allConection.Add(new Connection(allLocations[i * size + j], allLocations[i * size + j + 1], 4));
        // Вниз
        //Console.WriteLine("{0} {1}", i + j * size, i + (j + 1) * size);
        allConection.Add(new Connection(allLocations[i + j * size], allLocations[i + (j + 1) * size], 4));
        // Влево
        // Вверх
    }

Влево и вверх не знаю (но представляю: реализовать конструктор, который определяет двунаправленную связь) как, так как примера нет.

Сообщение от Yukikaze

Как должен выглядеть алгоритм для вышеприведенной таблицы если точки соединяются только со смежными, то есть 1 - 2, 2 - 3, и вниз 1 - 11, 11 - 21 и т.д

Добавлено через 10 минут

Сообщение от Yukikaze

Как сделать связь по диагонали я так и не понял

Проще простого:

C#
1
2
3
4
5
6
7
8
9
10
11
int size = (int)Math.Sqrt(allLocations.Count);
int last = size - 1; // Последний элемент
for (int i = 0; i < size - 1; i++)
{
    // Диагональ с верхнего левого в нижний правый угол
    //Console.WriteLine("{0} {1}", i * size + i, (i + 1) * size + i + 1);
    allConection.Add(new Connection(allLocations[i * size + i], allLocations[(i + 1) * size + i + 1], 4));
    // Диагональ с верхнего правого в нижний левый угол
    //Console.WriteLine("{0} {1}", i * size + last - i, (i + 1) * size + last - (i + 1));
    allConection.Add(new Connection(allLocations[i * size + last - i], allLocations[(i + 1) * size + last - (i + 1)], 4));
}

@Yukikaze · 04.02.2012, 17:12 **[ТС]**

Blood-Angel, ты мой бог, я хочу от тебя детей

ЗЫ Выше не копипаст

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Yukikaze 352 / 331 / 49 Регистрация: 12.12.2011 Сообщений: 563
	04.02.2012, 17:12 [ТС]
	Blood-Angel, ты мой бог, я хочу от тебя детей ЗЫ Выше не копипаст 0