Задача про найкоротші шляхи з заданої вершини до всіх інших (single-source shortest path problem).
Алгоритм застосовується лише для графів без ребер від'ємної ваги та петель.
Дано граф:
Знайти найкоротший шлях з вершини 1 до вершини 5.
H - множина відвіданих вершин
D[i] - поточне найкоротше відоме відстань з вершини s до вершини j
Prev[i] - номер вершини, що передує i у шляху
Встановлюємо D[i] = ∞ для всіх вершин, крім початкової
D[s] = 0
Поміщаємо всі вершини у чергу з пріоритетом Q (min-heap), де пріоритет вершини i - значення D[i]
public static class Dijkstra
{
///
/// Знаходить вершину з мінімальною відстанню серед невідвіданих
///
/// Масив відстаней
/// Масив відвіданих вершин
/// Кількість вершин
/// Індекс вершини з мінімальною відстанню
private static int FindMinDistanceVertex(int[] distance, bool[] shortestPathTreeSet, int verticesCount)
{
int minDistance = int.MaxValue;
int minIndex = 0;
for (int v = 0; v < verticesCount; ++v)
{
if (!shortestPathTreeSet[v] && distance[v] <= minDistance)
{
minDistance = distance[v];
minIndex = v;
}
}
return minIndex;
}
///
/// Виводить результати обчислення відстаней
///
/// Масив відстаней
/// Кількість вершин
private static void PrintDistances(int[] distance, int verticesCount)
{
Console.WriteLine("Вершина Відстань від джерела");
for (int i = 0; i < verticesCount; ++i)
Console.WriteLine("{0}\t {1}", i, distance[i]);
}
}
///
/// Реалізація алгоритму Дейкстри для знаходження найкоротших шляхів у графі
///
/// Матриця суміжності графа
/// Початкова вершина
/// Кількість вершин у графі
public static void DijkstraAlgo(int[,] graph, int source, int verticesCount)
{
// Ініціалізація масивів
int[] distance = new int[verticesCount]; // Масив найкоротших відстаней
bool[] visitedVertices = new bool[verticesCount]; // Масив відвіданих вершин
// Початкова ініціалізація
for (int i = 0; i < verticesCount; i++)
{
distance[i] = int.MaxValue; // Встановлюємо початкові відстані як "нескінченність"
visitedVertices[i] = false; // Позначаємо всі вершини як невідвідані
}
// Відстань від початкової вершини до самої себе завжди 0
distance[source] = 0;
// Основний цикл алгоритму
for (int count = 0; count < verticesCount - 1; count++)
{
// Знаходимо вершину з мінімальною відстанню серед невідвіданих
int currentVertex = FindMinDistanceVertex(distance, visitedVertices, verticesCount);
visitedVertices[currentVertex] = true; // Позначаємо вершину як відвідану
// Оновлюємо відстані до сусідніх вершин
for (int neighbor = 0; neighbor < verticesCount; neighbor++)
{
// Перевіряємо умови для релаксації ребра:
// 1. Вершина ще не відвідана
// 2. Існує ребро між currentVertex і neighbor (graph[currentVertex, neighbor] != 0)
// 3. Відстань до currentVertex не є нескінченністю
// 4. Нова відстань коротша за поточну
if (!visitedVertices[neighbor] &&
graph[currentVertex, neighbor] != 0 &&
distance[currentVertex] != int.MaxValue &&
distance[currentVertex] + graph[currentVertex, neighbor] < distance[neighbor])
{
distance[neighbor] = distance[currentVertex] + graph[currentVertex, neighbor];
}
}
}
// Вивід результатів
PrintDistances(distance, verticesCount);
}
using System;
class Program
{
static void Main(string[] args)
{
// Матриця суміжності графа (ваги ребер)
int[,] graph = {
{ 0, 6, 0, 0, 0, 0, 0, 0, 0 }, // Вершина 0
{ 6, 0, 9, 0, 0, 0, 0, 11, 0 }, // Вершина 1
{ 0, 9, 0, 5, 0, 6, 0, 0, 2 }, // Вершина 2
{ 0, 0, 5, 0, 9, 16, 0, 0, 0 }, // Вершина 3
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 }, // Вершина 4
{ 0, 0, 6, 0, 10, 0, 2, 0, 0 }, // Вершина 5
{ 0, 0, 0, 16, 0, 2, 0, 1, 6 }, // Вершина 6
{ 9, 11, 0, 0, 0, 0, 1, 0, 5 }, // Вершина 7
{ 0, 0, 2, 0, 0, 0, 6, 5, 0 } // Вершина 8
};
Console.WriteLine("Починаємо обчислення найкоротших шляхів за алгоритмом Дейкстри");
Console.WriteLine("-----------------------------------------------------------");
// Виклик алгоритму Дейкстри з початковою вершиною 0
Dijkstra.DijkstraAlgo(graph, 0, 9);
Console.WriteLine("\nНатисніть будь-яку клавішу для виходу...");
Console.ReadKey();
}
}
Використовано наш проект візуалізації графа як основу.
namespace GraphVisualization
{
partial class Form1
{
/// <summary>
/// Required designer variable.
/// </summary>
private System.ComponentModel.IContainer components = null;
/// <summary>
/// Clean up any resources being used.
/// </summary>
/// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}
#region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.menuStrip1 = new System.Windows.Forms.MenuStrip();
this.graphToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.newGraphToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.clearToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.matrixToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.generateMatrixToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.findShortestPathToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
this.pictureBox = new System.Windows.Forms.PictureBox();
this.dataGridViewPoints = new System.Windows.Forms.DataGridView();
this.dataGridViewMatrix = new System.Windows.Forms.DataGridView();
this.labelPoints = new System.Windows.Forms.Label();
this.labelMatrix = new System.Windows.Forms.Label();
this.comboBoxStartVertex = new System.Windows.Forms.ComboBox();
this.comboBoxEndVertex = new System.Windows.Forms.ComboBox();
this.labelStartVertex = new System.Windows.Forms.Label();
this.labelEndVertex = new System.Windows.Forms.Label();
this.menuStrip1.SuspendLayout();
((System.ComponentModel.ISupportInitialize)(this.pictureBox)).BeginInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewPoints)).BeginInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewMatrix)).BeginInit();
this.SuspendLayout();
//
// menuStrip1
//
this.menuStrip1.Items.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.graphToolStripMenuItem,
this.matrixToolStripMenuItem});
this.menuStrip1.Location = new System.Drawing.Point(0, 0);
this.menuStrip1.Name = "menuStrip1";
this.menuStrip1.Size = new System.Drawing.Size(980, 24);
this.menuStrip1.TabIndex = 0;
this.menuStrip1.Text = "menuStrip1";
//
// graphToolStripMenuItem
//
this.graphToolStripMenuItem.DropDownItems.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.newGraphToolStripMenuItem,
this.clearToolStripMenuItem});
this.graphToolStripMenuItem.Name = "graphToolStripMenuItem";
this.graphToolStripMenuItem.Size = new System.Drawing.Size(51, 20);
this.graphToolStripMenuItem.Text = "Graph";
//
// newGraphToolStripMenuItem
//
this.newGraphToolStripMenuItem.Name = "newGraphToolStripMenuItem";
this.newGraphToolStripMenuItem.Size = new System.Drawing.Size(121, 22);
this.newGraphToolStripMenuItem.Text = "Generate";
this.newGraphToolStripMenuItem.Click += new System.EventHandler(this.newGraphToolStripMenuItem_Click);
//
// clearToolStripMenuItem
//
this.clearToolStripMenuItem.Name = "clearToolStripMenuItem";
this.clearToolStripMenuItem.Size = new System.Drawing.Size(121, 22);
this.clearToolStripMenuItem.Text = "Clear";
this.clearToolStripMenuItem.Click += new System.EventHandler(this.clearToolStripMenuItem_Click);
//
// matrixToolStripMenuItem
//
this.matrixToolStripMenuItem.DropDownItems.AddRange(new System.Windows.Forms.ToolStripItem[] {
this.generateMatrixToolStripMenuItem,
this.findShortestPathToolStripMenuItem});
this.matrixToolStripMenuItem.Name = "matrixToolStripMenuItem";
this.matrixToolStripMenuItem.Size = new System.Drawing.Size(53, 20);
this.matrixToolStripMenuItem.Text = "Matrix";
//
// generateMatrixToolStripMenuItem
//
this.generateMatrixToolStripMenuItem.Name = "generateMatrixToolStripMenuItem";
this.generateMatrixToolStripMenuItem.Size = new System.Drawing.Size(180, 22);
this.generateMatrixToolStripMenuItem.Text = "Generate";
this.generateMatrixToolStripMenuItem.Click += new System.EventHandler(this.generateMatrixToolStripMenuItem_Click);
//
// findShortestPathToolStripMenuItem
//
this.findShortestPathToolStripMenuItem.Name = "findShortestPathToolStripMenuItem";
this.findShortestPathToolStripMenuItem.Size = new System.Drawing.Size(180, 22);
this.findShortestPathToolStripMenuItem.Text = "Find Shortest Path";
this.findShortestPathToolStripMenuItem.Click += new System.EventHandler(this.findShortestPathToolStripMenuItem_Click);
//
// pictureBox
//
this.pictureBox.BorderStyle = System.Windows.Forms.BorderStyle.FixedSingle;
this.pictureBox.Location = new System.Drawing.Point(12, 27);
this.pictureBox.Name = "pictureBox";
this.pictureBox.Size = new System.Drawing.Size(400, 400);
this.pictureBox.TabIndex = 1;
this.pictureBox.TabStop = false;
this.pictureBox.Click += new System.EventHandler(this.pictureBox_Click);
//
// dataGridViewPoints
//
this.dataGridViewPoints.AllowUserToAddRows = false;
this.dataGridViewPoints.AllowUserToDeleteRows = false;
this.dataGridViewPoints.AllowUserToResizeColumns = false;
this.dataGridViewPoints.AllowUserToResizeRows = false;
this.dataGridViewPoints.ColumnHeadersHeightSizeMode = System.Windows.Forms.DataGridViewColumnHeadersHeightSizeMode.AutoSize;
this.dataGridViewPoints.Enabled = false;
this.dataGridViewPoints.Location = new System.Drawing.Point(420, 43);
this.dataGridViewPoints.Name = "dataGridViewPoints";
this.dataGridViewPoints.Size = new System.Drawing.Size(160, 384);
this.dataGridViewPoints.TabIndex = 2;
//
// dataGridViewMatrix
//
this.dataGridViewMatrix.AllowUserToAddRows = false;
this.dataGridViewMatrix.AllowUserToDeleteRows = false;
this.dataGridViewMatrix.AllowUserToResizeColumns = false;
this.dataGridViewMatrix.AllowUserToResizeRows = false;
this.dataGridViewMatrix.ColumnHeadersHeightSizeMode = System.Windows.Forms.DataGridViewColumnHeadersHeightSizeMode.AutoSize;
this.dataGridViewMatrix.Location = new System.Drawing.Point(586, 43);
this.dataGridViewMatrix.Name = "dataGridViewMatrix";
this.dataGridViewMatrix.Size = new System.Drawing.Size(384, 384);
this.dataGridViewMatrix.TabIndex = 3;
//
// labelPoints
//
this.labelPoints.AutoSize = true;
this.labelPoints.Location = new System.Drawing.Point(482, 27);
this.labelPoints.Name = "labelPoints";
this.labelPoints.Size = new System.Drawing.Size(36, 13);
this.labelPoints.TabIndex = 4;
this.labelPoints.Text = "Points";
//
// labelMatrix
//
this.labelMatrix.AutoSize = true;
this.labelMatrix.Location = new System.Drawing.Point(735, 27);
this.labelMatrix.Name = "labelMatrix";
this.labelMatrix.Size = new System.Drawing.Size(87, 13);
this.labelMatrix.TabIndex = 5;
this.labelMatrix.Text = "Adjacency matrix";
//
// comboBoxStartVertex
//
this.comboBoxStartVertex.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
this.comboBoxStartVertex.FormattingEnabled = true;
this.comboBoxStartVertex.Location = new System.Drawing.Point(420, 450);
this.comboBoxStartVertex.Name = "comboBoxStartVertex";
this.comboBoxStartVertex.Size = new System.Drawing.Size(160, 21);
this.comboBoxStartVertex.TabIndex = 6;
this.comboBoxStartVertex.SelectedIndexChanged += new System.EventHandler(this.comboBoxStartVertex_SelectedIndexChanged);
//
// comboBoxEndVertex
//
this.comboBoxEndVertex.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
this.comboBoxEndVertex.FormattingEnabled = true;
this.comboBoxEndVertex.Location = new System.Drawing.Point(586, 450);
this.comboBoxEndVertex.Name = "comboBoxEndVertex";
this.comboBoxEndVertex.Size = new System.Drawing.Size(160, 21);
this.comboBoxEndVertex.TabIndex = 7;
this.comboBoxEndVertex.SelectedIndexChanged += new System.EventHandler(this.comboBoxEndVertex_SelectedIndexChanged);
//
// labelStartVertex
//
this.labelStartVertex.AutoSize = true;
this.labelStartVertex.Location = new System.Drawing.Point(420, 434);
this.labelStartVertex.Name = "labelStartVertex";
this.labelStartVertex.Size = new System.Drawing.Size(62, 13);
this.labelStartVertex.TabIndex = 8;
this.labelStartVertex.Text = "Start Vertex";
//
// labelEndVertex
//
this.labelEndVertex.AutoSize = true;
this.labelEndVertex.Location = new System.Drawing.Point(586, 434);
this.labelEndVertex.Name = "labelEndVertex";
this.labelEndVertex.Size = new System.Drawing.Size(59, 13);
this.labelEndVertex.TabIndex = 9;
this.labelEndVertex.Text = "End Vertex";
//
// Form1
//
this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
this.ClientSize = new System.Drawing.Size(980, 483);
this.Controls.Add(this.labelEndVertex);
this.Controls.Add(this.labelStartVertex);
this.Controls.Add(this.comboBoxEndVertex);
this.Controls.Add(this.comboBoxStartVertex);
this.Controls.Add(this.labelMatrix);
this.Controls.Add(this.labelPoints);
this.Controls.Add(this.dataGridViewMatrix);
this.Controls.Add(this.dataGridViewPoints);
this.Controls.Add(this.pictureBox);
this.Controls.Add(this.menuStrip1);
this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;
this.MainMenuStrip = this.menuStrip1;
this.Name = "Form1";
this.Text = "Graph Visualization - Dijkstra Algorithm";
this.menuStrip1.ResumeLayout(false);
this.menuStrip1.PerformLayout();
((System.ComponentModel.ISupportInitialize)(this.pictureBox)).EndInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewPoints)).EndInit();
((System.ComponentModel.ISupportInitialize)(this.dataGridViewMatrix)).EndInit();
this.ResumeLayout(false);
this.PerformLayout();
}
#endregion
private System.Windows.Forms.MenuStrip menuStrip1;
private System.Windows.Forms.ToolStripMenuItem graphToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem newGraphToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem clearToolStripMenuItem;
private System.Windows.Forms.PictureBox pictureBox;
private System.Windows.Forms.DataGridView dataGridViewPoints;
private System.Windows.Forms.DataGridView dataGridViewMatrix;
private System.Windows.Forms.Label labelPoints;
private System.Windows.Forms.Label labelMatrix;
private System.Windows.Forms.ToolStripMenuItem matrixToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem generateMatrixToolStripMenuItem;
private System.Windows.Forms.ToolStripMenuItem findShortestPathToolStripMenuItem;
private System.Windows.Forms.ComboBox comboBoxStartVertex;
private System.Windows.Forms.ComboBox comboBoxEndVertex;
private System.Windows.Forms.Label labelStartVertex;
private System.Windows.Forms.Label labelEndVertex;
}
}
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
namespace GraphVisualization
{
// Структура для представлення ребра графа
struct Edge
{
public MyPoint Point1; // Перша точка ребра
public MyPoint Point2; // Друга точка ребра
public int Weight; // Вага ребра (довжина)
// Конструктор ребра
public Edge(MyPoint point1, MyPoint point2, int weight)
{
Point1 = point1;
Point2 = point2;
Weight = weight;
}
}
// Структура для представлення точки графа
struct MyPoint
{
public int Id; // Ідентифікатор точки
public int X; // Координата X
public int Y; // Координата Y
// Конструктор точки
public MyPoint(int id, int x, int y)
{
Id = id;
X = x;
Y = y;
}
}
// Клас для зберігання інформації про вершину в алгоритмі Дейкстри
class DijkstraNode : IComparable<DijkstraNode>
{
public int VertexId { get; set; }
public int Distance { get; set; }
public int PreviousVertex { get; set; }
public DijkstraNode(int vertexId, int distance, int previousVertex = -1)
{
VertexId = vertexId;
Distance = distance;
PreviousVertex = previousVertex;
}
public int CompareTo(DijkstraNode other)
{
return Distance.CompareTo(other.Distance);
}
}
// Головна форма програми
public partial class Form1 : Form
{
private Bitmap bitmap; // Бітова карта для малювання
private List<MyPoint> points = new List<MyPoint>(); // Список точок
private List<Edge> edges = new List<Edge>(); // Список ребер
private List<Edge> shortestPathEdges = new List<Edge>(); // Ребра найкоротшого шляху
private Graphics graphics; // Графічний контекст
private int startVertexId = -1; // Початкова вершина для алгоритму Дейкстри
private int endVertexId = -1; // Кінцева вершина для алгоритму Дейкстри
// Константи для налаштування відображення
private const int Radius = 6;
private const int EdgeThickness = 2;
private const int ShortestPathThickness = 3;
private const int PointLabelFontSize = 12;
private const int EdgeLabelFontSize = 10;
private const string FontName = "Arial";
// Конструктор форми
public Form1()
{
InitializeComponent();
// Ініціалізація графічних компонентів
bitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
graphics = Graphics.FromImage(bitmap);
// Налаштування DataGridView для точок
dataGridViewPoints.Columns.Add("pointNumber", "№");
dataGridViewPoints.Columns.Add("pointСoordinates", "Point");
dataGridViewPoints.Columns[0].Width = 30;
dataGridViewPoints.Columns[1].Width = 70;
// Налаштування DataGridView для матриці
dataGridViewMatrix.RowHeadersWidth = 50;
// Додавання випадаючих списків для вибору вершин
comboBoxStartVertex.DropDownStyle = ComboBoxStyle.DropDownList;
comboBoxEndVertex.DropDownStyle = ComboBoxStyle.DropDownList;
}
// Обчислення довжини ребра між двома точками
private int EdgeLength(MyPoint point1, MyPoint point2)
{
return (int)Math.Sqrt(Math.Pow(point1.X - point2.X, 2) + Math.Pow(point1.Y - point2.Y, 2));
}
// Малювання точки на графіці
private void DrawPoint(MyPoint point, string text, Color color)
{
// Малювання кружечка
graphics.FillEllipse(new SolidBrush(color),
point.X - Radius, point.Y - Radius, Radius * 2, Radius * 2);
// Додавання текстової мітки
graphics.DrawString(text, new Font(FontName, PointLabelFontSize),
new SolidBrush(Color.Black), point.X + Radius, point.Y + Radius);
pictureBox.Image = bitmap;
}
// Заповнення матриці суміжності
private void FillMatrix(int number)
{
for (int i = 0; i < points.Count; i++)
{
for (int j = 0; j < points.Count; j++)
{
dataGridViewMatrix.Rows[i].Cells[j].Value = (i < j) ? number : 0;
}
}
}
// Генерація матриці суміжності
private void GenerateMatrix()
{
ClearMatrix();
// Додавання колонок до матриці
foreach (var point in points)
{
DataGridViewColumn column = new DataGridViewTextBoxColumn();
column.Name = $"{point.Id}";
column.Width = 25;
dataGridViewMatrix.Columns.Add(column);
}
// Додавання рядків до матриці
foreach (var point in points)
{
dataGridViewMatrix.Rows.Add();
dataGridViewMatrix.Rows[dataGridViewMatrix.Rows.Count - 1].HeaderCell.Value = $"{point.Id}";
}
FillMatrix(1);
// Центрування тексту в комірках
foreach (DataGridViewColumn column in dataGridViewMatrix.Columns)
{
column.DefaultCellStyle.Alignment = DataGridViewContentAlignment.MiddleCenter;
}
// Оновлення випадаючих списків
UpdateVertexComboBoxes();
}
// Оновлення випадаючих списків для вибору вершин
private void UpdateVertexComboBoxes()
{
comboBoxStartVertex.Items.Clear();
comboBoxEndVertex.Items.Clear();
foreach (var point in points)
{
comboBoxStartVertex.Items.Add($"{point.Id}");
comboBoxEndVertex.Items.Add($"{point.Id}");
}
if (comboBoxStartVertex.Items.Count > 0)
comboBoxStartVertex.SelectedIndex = 0;
if (comboBoxEndVertex.Items.Count > 0)
comboBoxEndVertex.SelectedIndex = 0;
}
// Генерація списку ребер на основі матриці
private void GenerateEdges()
{
edges.Clear();
for (int i = 0; i < points.Count; i++)
{
for (int j = 0; j < points.Count; j++)
{
if (i != j && Convert.ToInt32(dataGridViewMatrix.Rows[i].Cells[j].Value) == 1)
{
MyPoint p1 = new MyPoint(points[i].Id, points[i].X, points[i].Y);
MyPoint p2 = new MyPoint(points[j].Id, points[j].X, points[j].Y);
edges.Add(new Edge(p1, p2, EdgeLength(p1, p2)));
}
}
}
}
// Алгоритм Дейкстри для знаходження найкоротшого шляху
private void DijkstraAlgorithm()
{
if (edges.Count == 0 || startVertexId == -1 || endVertexId == -1)
return;
// Ініціалізація відстаней
int[] distances = new int[points.Count];
int[] previous = new int[points.Count];
bool[] visited = new bool[points.Count];
for (int i = 0; i < points.Count; i++)
{
distances[i] = int.MaxValue;
previous[i] = -1;
visited[i] = false;
}
distances[startVertexId] = 0;
// Пріоритетна черга для вершин
var priorityQueue = new SortedSet<DijkstraNode>(Comparer<DijkstraNode>.Create((x, y) =>
x.Distance != y.Distance ? x.Distance.CompareTo(y.Distance) : x.VertexId.CompareTo(y.VertexId)));
priorityQueue.Add(new DijkstraNode(startVertexId, 0));
while (priorityQueue.Count > 0)
{
var currentNode = priorityQueue.Min;
priorityQueue.Remove(currentNode);
int currentVertex = currentNode.VertexId;
if (visited[currentVertex]) continue;
visited[currentVertex] = true;
// Якщо досягли кінцевої вершини
if (currentVertex == endVertexId)
break;
// Отримання сусідів поточної вершини
foreach (var edge in edges)
{
int neighbor = -1;
if (edge.Point1.Id == currentVertex)
neighbor = edge.Point2.Id;
else if (edge.Point2.Id == currentVertex)
neighbor = edge.Point1.Id;
if (neighbor != -1 && !visited[neighbor])
{
int newDistance = distances[currentVertex] + edge.Weight;
if (newDistance < distances[neighbor])
{
distances[neighbor] = newDistance;
previous[neighbor] = currentVertex;
priorityQueue.Add(new DijkstraNode(neighbor, newDistance));
}
}
}
}
// Відновлення шляху
shortestPathEdges.Clear();
int current = endVertexId;
while (previous[current] != -1)
{
int prev = previous[current];
// Знаходження ребра між current і prev
var pathEdge = edges.FirstOrDefault(e =>
(e.Point1.Id == current && e.Point2.Id == prev) ||
(e.Point1.Id == prev && e.Point2.Id == current));
if (pathEdge.Point1.Id != -1) // Перевірка, що ребро знайдено
{
shortestPathEdges.Add(pathEdge);
}
current = prev;
}
// Виведення результату
if (distances[endVertexId] != int.MaxValue)
{
MessageBox.Show($"Найкоротший шлях від {startVertexId} до {endVertexId}: {distances[endVertexId]}");
}
else
{
MessageBox.Show("Шлях не знайдено");
}
}
// Малювання всіх точок
private void DrawPoints()
{
for (int i = 0; i < points.Count; i++)
{
Color pointColor = Color.Red;
if (i == startVertexId) pointColor = Color.Green;
else if (i == endVertexId) pointColor = Color.Blue;
DrawPoint(points[i], $"{i}", pointColor);
}
}
// Малювання всіх ребер
private void DrawEdges()
{
foreach (var edge in edges)
{
// Перевірка, чи ребро належить до найкоротшого шляху
bool isShortestPath = shortestPathEdges.Any(pe =>
(pe.Point1.Id == edge.Point1.Id && pe.Point2.Id == edge.Point2.Id) ||
(pe.Point1.Id == edge.Point2.Id && pe.Point2.Id == edge.Point1.Id));
Color edgeColor = isShortestPath ? Color.Red : Color.Chartreuse;
int thickness = isShortestPath ? ShortestPathThickness : EdgeThickness;
MyPoint p1 = edge.Point1;
MyPoint p2 = edge.Point2;
var label = edge.Weight.ToString();
var font = new Font(FontName, EdgeLabelFontSize);
var size = graphics.MeasureString(label, font, pictureBox.Size);
// Малювання лінії ребра
graphics.DrawLine(new Pen(edgeColor, thickness),
new Point(p1.X, p1.Y), new Point(p2.X, p2.Y));
// Додавання мітки з довжиною ребра
graphics.DrawString(label,
font, new SolidBrush(Color.Black),
(p1.X + p2.X) / 2 - size.Width / 2, (p1.Y + p2.Y) / 2 - size.Height / 2);
}
}
// Очищення графа
private void ClearGraph()
{
graphics.Clear(Color.White);
pictureBox.Image = bitmap;
points.Clear();
dataGridViewPoints.Rows.Clear();
shortestPathEdges.Clear();
startVertexId = -1;
endVertexId = -1;
comboBoxStartVertex.Items.Clear();
comboBoxEndVertex.Items.Clear();
}
// Очищення матриці
private void ClearMatrix()
{
dataGridViewMatrix.Rows.Clear();
dataGridViewMatrix.Columns.Clear();
}
// Обробник кліку на pictureBox для додавання нової точки
private void pictureBox_Click(object sender, EventArgs e)
{
int x = MousePosition.X - Location.X - pictureBox.Location.X - 8;
int y = MousePosition.Y - Location.Y - pictureBox.Location.Y - 32;
points.Add(new MyPoint(points.Count, x, y));
dataGridViewPoints.Rows.Add(points[points.Count - 1].Id, $"({x}; {y})");
DrawPoint(points[points.Count - 1], $"{points.Count - 1}", Color.Red);
}
// Обробник зміни вибору початкової вершини
private void comboBoxStartVertex_SelectedIndexChanged(object sender, EventArgs e)
{
if (comboBoxStartVertex.SelectedIndex >= 0)
{
startVertexId = comboBoxStartVertex.SelectedIndex;
Invalidate();
}
}
// Обробник зміни вибору кінцевої вершини
private void comboBoxEndVertex_SelectedIndexChanged(object sender, EventArgs e)
{
if (comboBoxEndVertex.SelectedIndex >= 0)
{
endVertexId = comboBoxEndVertex.SelectedIndex;
Invalidate();
}
}
// Обробник меню для генерації нового графа
private void newGraphToolStripMenuItem_Click(object sender, EventArgs e)
{
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges();
DrawEdges();
Invalidate();
}
// Обробник меню для очищення всього
private void clearToolStripMenuItem_Click(object sender, EventArgs e)
{
ClearGraph();
ClearMatrix();
}
// Обробник меню для генерації матриці
private void generateMatrixToolStripMenuItem_Click(object sender, EventArgs e)
{
GenerateMatrix();
}
// Обробник меню для знаходження найкоротшого шляху
private void findShortestPathToolStripMenuItem_Click(object sender, EventArgs e)
{
if (dataGridViewMatrix.Rows.Count < dataGridViewPoints.Rows.Count)
GenerateMatrix();
GenerateEdges();
DijkstraAlgorithm();
Invalidate();
}
// Перевизначення методу малювання форми
protected override void OnPaint(PaintEventArgs e)
{
graphics.Clear(Color.White);
pictureBox.Image = bitmap;
DrawPoints();
DrawEdges();
base.OnPaint(e);
}
}
}