ПРИЛОЖЕНИЯ. Кодпрограммы«Алгоритм Дейкстры для поиска кратчайшего пути»

Приложение 1.

Кодпрограммы«Алгоритм Дейкстры для поиска кратчайшего пути»

КодForm1.cs

using System;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

usingSystem.Windows.Forms;

namespacedeikstra

{

public partial class Form1 : Form

{

/// <summary>

/// Матрица смежености, по которой буде строиться граф

/// </summary>

privateint[,] matrixAdjacency = new int[,]

{

//1 2 3 4 5 6 7 8 9 10 11

{0, 6, 3, 2, 8, 0, 0, 0, 0, 0, 0},

{6, 0, 2, 0, 0, 0, 7, 8, 0, 0, 0},

{3, 2, 0, 0, 0, 6, 0, 12, 0, 0, 0},

{2, 0, 0, 0, 5, 0, 0, 0, 3, 0, 0},

{8, 0, 0, 5, 0, 14, 0, 0, 5, 0, 0},

{0, 0, 6, 0, 14, 0, 11, 6, 10, 0, 9},

{0, 0, 0, 0, 0, 11, 0, 0, 4, 12, 7},

{0, 8, 12, 0, 0, 6, 0, 0, 0, 0, 3},

{0, 0, 0, 3, 5, 10, 4, 0, 0, 2, 0},

{0, 0, 0, 0, 0, 0, 12, 0, 2, 0, 5},

{0, 0, 0, 0, 0, 9, 7, 3, 0, 5, 0}

};

/// <summary>

/// Списоквершинграфа

/// </summary>

private List<EdgeGraph>listEdgeG = new List<EdgeGraph>();

/// <summary>

/// Списокреберграфа

/// </summary>

private List<NodeGraph>listNodeG = new List<NodeGraph>();

privateintcnt = 1;

/// <summary>

/// Индексначальнойвершины

/// </summary>

privateintsrc_index;

/// <summary>

/// Индексконечнойвершины

/// </summary>

privateintdest_index;

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

for (inti = 0; i<matrixAdjacency.GetLength(0); ++i)

{

for (int j = 0; j <matrixAdjacency.GetLength(1); ++j)

{

if (i > j &&matrixAdjacency[i, j] != 0)

{

EdgeGraph edge = new EdgeGraph(listNodeG[i].point, listNodeG[j].point,

matrixAdjacency[i, j].ToString());

edge.draw_edge(pictureBox1.CreateGraphics(), 1);

listEdgeG.Add(edge);

}

}

}

foreach (var x in listNodeG)

{

x.draw_number(pictureBox1.CreateGraphics());

}

}

private void pictureBox1_Click(object sender, EventArgs e)

{

}

private void Form1_Load(object sender, EventArgs e)

{

label1.Text = "Напоминание: Разместите на форме " + (matrixAdjacency.GetLength(0)) + " вершин...";

}

privateintcheckCnt = 1;

privateint checkCnt1 = 1;

privatebool flag = true;

} /// <summary>

/// рисует вершини и выделяет зеленым цветом начальну и красным конечню вершину

/// </summary>

/// <param name="sender"></param>

/// <param name="e"></param>

private void pictureBox1_MouseDown(object sender, MouseEventArgs e)

{

//Рисуемсначаланашивершины

if (checkCnt<= matrixAdjacency.GetLength(0))

{

NodeGraphng = new NodeGraph(e.X, e.Y, (cnt++).ToString());

ng.draw_node(pictureBox1.CreateGraphics(), Color.Black); // черныеточки - вершины

listNodeG.Add(ng);

++checkCnt;

}

//фикисруем начальную и конечную вершины

else

{

for (inti = 0; i<listNodeG.Count; ++i)

{

if (checkCnt1 <= 2)

{

if (e.X>= listNodeG[i].point.X - 15 &&e.X<= listNodeG[i].point.X + 15

&&e.Y>= listNodeG[i].point.Y - 15 &&e.Y<= listNodeG[i].point.Y + 15)

{

if (flag == true)

{

src_index = i;

listNodeG[i].draw_node(pictureBox1.CreateGraphics(), Color.Chartreuse); // выделяемначальнуювершину

flag = false;

++checkCnt1;

}

else

{

dest_index = i;

listNodeG[i].draw_node(pictureBox1.CreateGraphics(), Color.Red); // выделяемконечнуювершину

++checkCnt1;

}

}

}

}

}

}

privatevoidbutton2_Click(objectsender, EventArgse) // Ищемивыделяемжирнымкратчайшийпутьотначальнойвершиныдоконечной

{

try

{

var list = GraphMethods.DoDijkstra(matrixAdjacency, src_index, dest_index);

for(inti = 0; i<list.Count - 1; ++i)

{

EdgeGraphedg = new EdgeGraph(listNodeG[list[i]].point, listNodeG[list[i + 1]].point);

edg.draw_edge(pictureBox1.CreateGraphics(), 4);

foreach (var x in listNodeG)

{

x.draw_number(pictureBox1.CreateGraphics());

}

}

}

catch (Exception ex)

{

MessageBox.Show(ex.Message);

}

}

private void button3_Click(object sender, EventArgs e) // вызываемперерисовкуэлементаиперезапускаем

{

pictureBox1.Image = null;

pictureBox1.Invalidate();

Application.Restart();

}

Код Graph.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

using System.Threading.Tasks;

namespacedeikstra

{

/// <summary>

/// Класс "граф"

/// </summary>

class Graph

{

/// <summary>

/// Списокребер

/// </summary>

Dictionary<int, Dictionary<int, int>> vertices = new Dictionary<int, Dictionary<int, int>>();

/// <summary>

/// Метод додавания вершины в список

/// </summary>

/// <param name="name"></param>

/// <param name="edges"></param>

public void add_vertex(int name, Dictionary<int, int> edges)

{

vertices[name] = edges;

}

/// <summary>

/// Нахождениекратчайшегопутимежду start и finish

/// </summary>

/// <param name="start"></param>

/// <param name="finish"></param>

/// <returns></returns>

public List<int>shortest_path(int start, int finish) // кратчайшийпуть

{

var previous = new Dictionary<int, int>();

var distances = new Dictionary<int, int>();

var nodes = new List<int>();

List<int> path = null;

foreach (var vertex in vertices)

{

if (vertex.Key == start)

{

distances[vertex.Key] = 0;

}

else

{

distances[vertex.Key] = int.MaxValue;

}

nodes.Add(vertex.Key);

}

while (nodes.Count != 0)

{

nodes.Sort((x, y) => distances[x] - distances[y]);

var smallest = nodes[0];

nodes.Remove(smallest);

if (smallest == finish)

{

path = new List<int>();

while (previous.ContainsKey(smallest))

{

path.Add(smallest);

smallest = previous[smallest];

}

break;

}

if (distances[smallest] == int.MaxValue)

{

break;

}

foreach (var neighbor in vertices[smallest])

{

var alt = distances[smallest] + neighbor.Value;

if (alt < distances[neighbor.Key])

{

distances[neighbor.Key] = alt;

previous[neighbor.Key] = smallest;

}

}

}

returnpath;

}

}

}

Код GraphMethods.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

using System.Threading.Tasks;

namespacedeikstra

{

/// <summary>

/// Класс "методыграфа"

/// </summary>

internal static class GraphMethods

{

/// <summary>

/// Метод преобразования матрицы смежености в список ребер и поиск кратчайшего пути

/// </summary>

/// <param name="m"></param>

/// <param name="s"></param>

/// <param name="e"></param>

/// <returns></returns>

static public List<int>DoDijkstra(int[,] m, int s, int e)

{

Graph g = new Graph();

for (inti = 0; i<m.GetLength(0); ++i)

{

Dictionary<int, int>buf = new Dictionary<int, int>();

for (int j = 0; j <m.GetLength(1); ++j)

if (m[i, j] != 0)

buf.Add(j, m[i, j]);

g.add_vertex(i, buf);

}

var l = g.shortest_path(s, e);

l.Add(s);

l.Reverse();

return l;

}

}

}

Код NodeGraph.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Drawing;

usingSystem.Linq;

usingSystem.Security.AccessControl;

using System.Security.Cryptography.X509Certificates;

usingSystem.Text;

usingSystem.Threading.Tasks;

using System.Windows.Forms;

namespacedeikstra

{

/// <summary>

/// Класс "Узелграфа"

/// </summary>

classNodeGraph

{

/// <summary>

/// Описываетузелграфакакточкунапикчербоксе

/// </summary>

public Point point { get; set; }

/// <summary>

/// Текствузле

/// </summary>

public string number { get; set; }

//перегрузкаконструкторов

publicNodeGraph()

{

point = new Point();

}

publicNodeGraph(int _X, int _Y, string _num)

{

point = new Point(_X, _Y);

number = _num;

}

publicNodeGraph(Point _p, string _num)

{

point = _p;

number = _num;

}

/// <summary>

/// Рисует узел по заданум цвету

/// </summary>

/// <param name="g"></param>

/// <param name="color"></param>

public void draw_node(Graphics g, Color color)

{

g.DrawEllipse(new Pen(Color.Black), point.X - 13, point.Y - 12, 30, 30);

g.FillEllipse(new SolidBrush(color), point.X - 13, point.Y - 12, 30, 30);

draw_number(g);

g.Dispose();

}

/// <summary>

/// Рисует текст в узле, в даном случае число

/// </summary>

/// <param name="g"></param>

public void draw_number(Graphics g)

{

Font font = new Font("Times New Roman", 12, FontStyle.Bold);

g.DrawString(number, font, new SolidBrush(Color.Blue), point.X - 4, point.Y - 5);

g.Dispose();

}

}

}