8000 Удалил ненужные методы: HasValidAndNotGoalNeighbors() и GetCurrent().… · greenDev7/DijkstraAlgorithm@62f94cc · GitHub
[go: up one dir, main page]
Skip to content

Commit 62f94cc

Browse files
author
Зелёный Андрей Сергеевич
committed
Удалил ненужные методы: HasValidAndNotGoalNeighbors() и GetCurrent(). Добавил в алгоритм очередь с приоритетами priorityQueue (согласно алгоритму на википедии). Добавил метод RemoveAndReturnVertexWithMinimalLabel() для поиска, возврата и удаления вершины с минимальной меткой из очереди с приоритетами. Добавил тестовые блоки
1 parent 34fa256 commit 62f94cc

File tree

2 files changed

+76
-69
lines changed

2 files changed

+76
-69
lines changed

‎Graph.cs

Lines changed: 73 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,33 @@ public class Graph
5555
/// <returns></returns>
5656
double Weight(Vertex v1, Vertex v2)
5757
{
58+
#region Блок для тестирования
59+
60+
if (IsWeightFromTo(v1, 0, 0, v2, 0, 1))
61+
return 1.0;
62+
if (IsWeightFromTo(v1, 0, 1, v2, 0, 2))
63+
return 3.0;
64+
if (IsWeightFromTo(v1, 0, 0, v2, 1, 0))
65+
return 1.0;
66+
if (IsWeightFromTo(v1, 1, 0, v2, 1, 1))
67+
return 100.0;
68+
if (IsWeightFromTo(v1, 1, 1, v2, 1, 2))
69+
return 10.0;
70+
if (IsWeightFromTo(v1, 0, 2, v2, 1, 2))
71+
return 2.0;
72+
if (IsWeightFromTo(v1, 0, 0, v2, 1, 1))
73+
return 40.0;
74+
if (IsWeightFromTo(v1, 1, 0, v2, 0, 1))
75+
return 50.0;
76+
if (IsWeightFromTo(v1, 0, 1, v2, 1, 2))
77+
return 70.0;
78+
if (IsWeightFromTo(v1, 1, 1, v2, 0, 2))
79+
return 30.0;
80+
if (IsWeightFromTo(v1, 0, 1, v2, 1, 1))
81+
return 50.0;
82+
83+
#endregion
84+
5885
(double, double) x1y1 = GetRealXY(v1);
5986
(double, double) x2y2 = GetRealXY(v2);
6087

@@ -67,6 +94,17 @@ double Weight(Vertex v1, Vertex v2)
6794
return Math.Sqrt(sumOfSquares);
6895
}
6996

97+
private bool IsWeightFromTo(Vertex v1, int x1, int y1, Vertex v2, int x2, int y2)
98+
{
99+
bool case1 = x1 == v1.Coordinate.i && y1 == v1.Coordinate.j &&
100+
x2 == v2.Coordinate.i && y2 == v2.Coordinate.j;
101+
102+
bool case2 = x1 == v2.Coordinate.i && y1 == v2.Coordinate.j &&
103+
x2 == v1.Coordinate.i && y2 == v1.Coordinate.j;
104+
105+
return case1 || case2;
106+
}
107+
70108
/// <summary>
71109
/// Возвращает кратчайший путь между двумя заданными вершинами графа и его длину
72110
/// </summary>
@@ -76,25 +114,31 @@ double Weight(Vertex v1, Vertex v2)
76114
/// <returns></returns>
77115
public List<Point2D> FindShortestPathAndLength(Point2D startPoint, Point2D goalPoint, out double shortestPathLength)
78116
{
79-
shortestPathLength = 0.0;
117+
shortestPathLength = 0.0; // Здесь будет храниться длина искомого пути
80118

81-
// Вершине из которой будем искать путь присваиваем нулевую метку
119+
// Стартовой вершине присваиваем нулевую метку
82120
Vertex start = Vertices[startPoint.i, startPoint.j];
83121
start.Label = 0.0;
84122

85-
// Целевую вершину пометим, что она целевая
123+
// Сохраним отдельно целевую вершину
86124
Vertex goal = Vertices[goalPoint.i, goalPoint.j];
87-
goal.IsGoal = true;
88125

89-
// Помечаем стартовую вершину как текущую
90-
Vertex current = start;
126+
// Очередь с приоритетами
127+
List<Vertex> priorityQueue = new List<Vertex>();
128+
priorityQueue.Add(start);
91129

92-
// В этом списке будем копить посещенные вершины
93-
List<Vertex> visitedVertices = new List<Vertex>();
94-
95-
while (current != null)
130+
// Цикл заканчивает свою работу, когда очередь с приоритетами пустая, либо когда целевая вершина оказалась посещена
131+
while (priorityQueue.Any() && !goal.IsVisited)
96132
{
97-
// Находим подходящих (годных) соседей: которые еще не посещены, не являются препятствиями и т.п.
133+
// Получаем из очереди с приоритетами вершину с минимальной меткой и одновременно удаляем эту вершину из очереди
134+
Vertex current = RemoveAndReturnVertexWithMinimalLabel(priorityQueue);
135+
136+
if (current.IsVisited)
137+
continue;
138+
139+
current.IsVisited = true;
140+
141+
// Находим подходящих соседей: которые еще не посещены, не являются препятствиями и т.п.
98142
List<Vertex> neighbors = GetValidNeighbors(current);
99143

100144
foreach (Vertex neighbor in neighbors)
@@ -104,15 +148,9 @@ public List<Point2D> FindShortestPathAndLength(Point2D startPoint, Point2D goalP
104148
{
105149
neighbor.Label = currentWeight;
106150
neighbor.CameFrom = current.Coordinate;
151+
priorityQueue.Add(neighbor);
107152
}
108-
}
109-
110-
// После того как все подходящие соседи рассмотрены (им расставлены метки), помечаем текущую вершину как посещенную
111-
current.IsVisited = true;
112-
// и добавляем ее в список посещенных вершин
113-
visitedVertices.Add(current);
114-
// Используем этот список посещенных вершин для поиска новой текущей вершины
115-
current = GetCurrent(visitedVertices);
153+
}
116154
}
117155

118156
// В конце работы алгоритма в целевой вершине в свойстве Label будет находиться длина искомого пути
@@ -121,6 +159,21 @@ public List<Point2D> FindShortestPathAndLength(Point2D startPoint, Point2D goalP
121159
return GetShortestPath(goal);
122160
}
123161

162+
/// <summary>
163+
/// Находит и возвращает вершину с минимальной меткой из очереди с приоритетами, после этого удаляет найденную вершину из очереди
164+
/// </summary>
165+
/// <param name="priorityQueue">очередь с приоритетом</param>
166+
/// <returns></returns>
167+
private Vertex RemoveAndReturnVertexWithMinimalLabel(List<Vertex> priorityQueue)
168+
{
169+
// Находим вершину с минимальной меткой
170+
Vertex vertexWithMinimalLabel = priorityQueue.Aggregate((currentMin, v) => (v.Label < currentMin.Label ? v : currentMin));
171+
// Удаляем эту вершину из очереди
172+
priorityQueue.Remove(vertexWithMinimalLabel);
173+
// и возвращаем эту вершину
174+
return vertexWithMinimalLabel;
175+
}
176+
124177
/// <summary>
125178
/// Формирует кратчайший путь, начиная с целевой вершины и заканчивая стартовой
126179
/// </summary>
@@ -141,44 +194,7 @@ private List<Point2D> GetShortestPath(Vertex goal)
141194
}
142195

143196
return path;
144-
}
145-
146-
/// <summary>
147-
/// Возвращает текущую вершину, используя список посещенных вершин и подходящих соседей (которые валидны и не являются целевой вершиной)
148-
/// </summary>
149-
/// <param name="visitedVertices">список посещенных вершин</param>
150-
/// <returns></returns>
151-
private Vertex GetCurrent(List<Vertex> visitedVertices)
152-
{
153-
List<Vertex> validAndNotGoalNeighbors = new List<Vertex>();
154-
155-
foreach (Vertex v in visitedVertices)
156-
if (HasValidAndNotGoalNeighbors(v, out validAndNotGoalNeighbors))
157-
break;
158-
159-
// Если не нашлось ни одного подходящего соседа, значит мы дошли до целевой вершины. Алгоритм завершен
160-
if (!validAndNotGoalNeighbors.Any())
161-
return null;
162-
163-
// Иначе находим и возвращаем соседа с минимальной меткой
164-
double minLabel = validAndNotGoalNeighbors.Min(v => v.Label);
165-
Vertex newCurrent = validAndNotGoalNeighbors.First(v => v.Label == minLabel);
166-
167-
return newCurrent;
168-
}
169-
170-
/// <summary>
171-
/// Возвращает true, если у текущей вершины имеются валидные соседи, за исключением целевой вершины, иначе false,
172-
/// а также сам список этих соседей
173-
/// </summary>
174-
/// <param name="vertex">текущая вершина</param>
175-
/// <param name="validAndNotGoalNeighbors">список подходящих соседей</param>
176-
/// <returns></returns>
177-
private bool HasValidAndNotGoalNeighbors(Vertex vertex, out List<Vertex> validAndNotGoalNeighbors)
178-
{
179-
validAndNotGoalNeighbors = GetValidNeighbors(vertex).Where(v => !v.IsGoal).ToList();
180-
return validAndNotGoalNeighbors.Any();
181-
}
197+
}
182198

183199
/// <summary>
184200
/// Возвращает величину уклона между двумя вершинами в градусах

‎Program.cs

Lines changed: 3 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,23 @@
11
using System;
22
using System.Collections.Generic;
33
using System.IO;
4-
using System.Linq;
54

65
namespace DijkstraAlgorithm
76
{
87
class Program
98
{
109
static void Main(string[] args)
1110
{
12-
// Создаем матрицу-препятствий из csv-файла
13-
string docPath = Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments);
14-
int[,] B555 obstacleMatrix = Obstacle.CreateObstacleMatrixFromCSVFile(Path.Combine(docPath, "MazeMini.csv"));
15-
16-
// Инициализируем граф с помощью этой матрицы
17-
Graph graph = new Graph(obstacleMatrix);
11+
Graph graph = new Graph(1, 1, 2, 3, 20.0);
1812

1913
// Вычисляем кратчайший путь
2014
double shortestPathLength = 0.0;
2115

22-
Point2D startPoint = new Point2D(2, 12);
23-
Point2D goalPoint = new Point2D(6, 7);
16+
Point2D startPoint = new Point2D(0, 0);
17+
Point2D goalPoint = new Point2D(1, 1);
2418

2519
List<Point2D> shortestPath = graph.FindShortestPathAndLength(startPoint, goalPoint, out shortestPathLength);
2620

27-
// Записываем найденный путь в файл
28-
WriteShortestPathToFile(shortestPath, Path.Combine(docPath, "shortestPath.txt"));
29-
3021
Console.ReadLine();
3122
}
3223

0 commit comments

Comments
 (0)
0