 |
|
РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ
Результат работы программ
Входные данные представлены на рисунке 3:
Рисунок 3 – входные данные
Выходные данные (по нажатию на кнопку «Показать кратчайший путь») представлены на рисунке 4:
Рисунок 4 – выходные данные
Руководство пользователя
1.Запускаем программу
2. Указываем произвольно 11 вершин в Рабочей Области
3. Нажимаем на кнопку «Построить граф»
4. Выбираем начальную и конечную вершины. Сначала будет выбрана начальная точка (зеленым), а потом конечная(красным).
5. Для вычисления кратчайшего пути от заданных точек нажмите кнопку «Показать кратчайший путь»
Если пользователю необходимо построить новый граф с новыми вершинами и ребрами, нужно нажать кнопку «Очистить» после чего Рабочая Область будет очищена и готова к работе.
ЗАКЛЮЧЕНИЕ
В ходе выполнения курсовой работы были выполнены все поставленные задачи, а так же был получен дополнительный опыт разработки приложений на языке C# с применением алгоритма Дейкстры.
Результатом выполнения является работоспособная программа, способная задавать вершины, строить граф и находить кратчайший путь между указанными точками.
Были максимально предусмотрены всевозможные ошибки, которые могут возникнуть при использовании данной программы, однако это не исключает возможность их появления.
Программа не требует больших ресурсных затрат, интерфейс рассчитан на простого пользователя.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1) Герберт Шилдт. «Полный справочник по C#» [Текст] / Герберт Шилдт. – ООО «И.Д. Вильямс», 2010. – 780 с.
2) CLR via C#. Программирование на платформе Microsoft .NET Framework 4.5 на языке C#. 4-е изд. [Текст] / Дж.Рихтер – Москва: Дом Книги, 2011.
3) Бьёрн Страуструп «Язык программирования C#». [Текст] / Бьёрн Страуструп – Специальное издание. Москва: Бином-Пресс, 2010. — 1104 с.
4) Язык программирования C#. Классика Computers Science. 4-е изд. [Текст] / А. Хейлсерберг, М. Торгерсен — БХВ-Петербург, 2011. — С. 336.
5) Изучаем C#. 3-е изд. [Текст] / Э. Стиллмен— М.: ДМК Пресс, 2011. — С. 304.
ПРИЛОЖЕНИЯ
Приложение 1.
Код программы «Алгоритм Дейкстры для поиска кратчайшего пути»
Код Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace deikstra
{
public partial class Form1 : Form
{
/// <summary>
/// Матрица смежености, по которой буде строиться граф
/// </summary>
private int[,] 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>();
private int cnt = 1;
/// <summary>
/// Индекс начальной вершины
/// </summary>
private int src_index;
/// <summary>
/// Индекс конечной вершины
/// </summary>
private int dest_index;
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
for (int i = 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)) + " вершин...";
}
private int checkCnt = 1;
private int checkCnt1 = 1;
private bool 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))
{
NodeGraph ng = new NodeGraph(e.X, e.Y, (cnt++).ToString());
ng.draw_node(pictureBox1.CreateGraphics(), Color.Black); // черные точки - вершины
listNodeG.Add(ng);
++checkCnt;
}
//фикисруем начальную и конечную вершины
else
{
for (int i = 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;
}
}
}
}
}
}
private void button2_Click(object sender, EventArgs e) // Ищем и выделяем жирным кратчайший путь от начальной вершины до конечной
{
try
{
var list = GraphMethods.DoDijkstra(matrixAdjacency, src_index, dest_index);
for(int i = 0; i < list.Count - 1; ++i)
{
EdgeGraph edg = 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;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace deikstra
{
/// <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;
}
}
}
return path;
}
}
}
Код GraphMethods.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace deikstra
{
/// <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 (int i = 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;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Security.AccessControl;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace deikstra
{
/// <summary>
/// Класс "Узел графа"
/// </summary>
class NodeGraph
{
/// <summary>
/// Описывает узел графа как точку на пикчербоксе
/// </summary>
public Point point { get; set; }
/// <summary>
/// Текст в узле
/// </summary>
public string number { get; set; }
//перегрузка конструкторов
public NodeGraph()
{
point = new Point();
}
public NodeGraph(int _X, int _Y, string _num)
{
point = new Point(_X, _Y);
number = _num;
}
public NodeGraph(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();
}
}
}