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

Приложение 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();

}

}

}