Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
"Санкт-Петербургский государственный морской технический университет"
Кафедра прикладной математики и математического моделирования
КУРСОВАЯ РАБОТА
по дисциплине "Структуры и алгоритмы"
на тему
"Алгоритм Дейкстры"
|
ИСПОЛНИТЕлЬ |
||
|
Студент группы 1290 |
Е. С. Александрова |
|
|
РУКОВОДИТЕЛЬ |
||
|
Преподаватель |
А.Я. Войткунская |
Санкт-Петербург
2012
1. Постановка задачи 3
2. Алгоритм 3
3. Листинг 3
4. Тестирование 10
5. Вывод 13
6. Список использованных источников 13
Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстройв 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях.
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
3. ЛИСТИНГ
Класс Graph.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Дейкстры
{
class Graph
{
public int[,] arrMatrix;
public int[,] ReadGraphWeight(int nQuantity)
{
arrMatrix = new int[nQuantity, nQuantity];
for (int i = 0; i < nQuantity; i++)
for (int j = 0; j < nQuantity; j++)
arrMatrix[i,j] = 0;
for (int i = 0; i < nQuantity; i++)
for (int j = i+1; j < nQuantity; j++)
{
Console.Write("Введите вес ребра [{0},{1}] = ",i+1,j+1);
arrMatrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
Console.WriteLine();
return arrMatrix;
}
public int[,] PrintGraphWeight(int [,] Matrix)
{
for (int i = 0; i < Matrix.GetLength(0); i++)
Console.Write(" X{0}", i + 1);
Console.WriteLine("\n\n");
for (int i = 0; i < Matrix.GetLength(0); i++)
{
Console.Write("X{0} ", i + 1);
for (int j = 0; j < Matrix.GetLength(0); j++)
{
Console.Write("{0} ", Matrix[i,j]);
Matrix[j,i] = Matrix[i,j];
}
Console.WriteLine("\n\n");
}
for (int i = 0; i < Matrix.GetLength(0); i++)
for (int j = 0; j < Matrix.GetLength(0); j++)
if (Matrix[i,j] == 0) Matrix[i,j] = 65535;
return Matrix;
}
public int[,] AddEdge(int[,] arrMatrix)
{
Console.WriteLine("\nВведите количество ребер, которые вы хотите добавить");
int nNumber = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < nNumber; i++)
{
Console.WriteLine("\nВведите точку начала ребра.");
int nFirst = Convert.ToInt32(Console.ReadLine())-1;
Console.WriteLine("\nВведите точку конца ребра.");
int nEnd = Convert.ToInt32(Console.ReadLine())-1;
Console.WriteLine("\nВведите вес ребра.");
int nWeight = Convert.ToInt32(Console.ReadLine());
arrMatrix[nFirst, nEnd] = nWeight;
}
for (int i = 0; i < arrMatrix.GetLength(0); i++)
for (int j = 0; j < arrMatrix.GetLength(0); j++)
if (arrMatrix[i, j] == 65535)
arrMatrix[i, j] = 0;
Console.WriteLine();
return arrMatrix;
}
public int[,] AddPoints(int[,] arrMatrix)
{
Console.WriteLine("\nВведите количество вершин, которые вы хотите добавить.");
int nNumber = Convert.ToInt32(Console.ReadLine());
Console.WriteLine();
int[,] arrNewMatrix = new int[arrMatrix.GetLength(0)+nNumber, arrMatrix.GetLength(0)+nNumber];
for (int i = 0; i < arrNewMatrix.GetLength(0); i++)
for (int j = i + 1; j < arrNewMatrix.GetLength(0); j++)
if ((i < arrMatrix.GetLength(0)) && (j < arrMatrix.GetLength(0)))
arrNewMatrix[i, j] = arrMatrix[i, j];
else
{
if (arrNewMatrix[i, j] == 65535)
arrNewMatrix[i, j] = 0;
Console.WriteLine("Введите [{0},{1}]", i + 1, j + 1);
arrNewMatrix[i, j] = Convert.ToInt32(Console.ReadLine());
if (arrNewMatrix[i, j] == 0)
arrNewMatrix[i, j] = 65535;
}
Console.WriteLine();
return arrNewMatrix;
}
public void End(int[,] arrMatrix)
{
int[,] Matrix = new int[arrMatrix.GetLength(0), arrMatrix.GetLength(0)];
Console.WriteLine("\n Введите 0, если хотите выйти из программы, \nВведите 1, если хотите добавить ребро, \nВведите 2, если хотите добавить вершину, \nВведите 3, если хотите запустить алгоритм ещё раз");
int nNumber = Convert.ToInt32(Console.ReadLine());
Matrix = arrMatrix;
while (nNumber != 0)
{
if (nNumber == 1)
{
Matrix=AddEdge(arrMatrix);
PrintGraphWeight(Matrix);
}
if (nNumber == 2)
{
Matrix=AddPoints(arrMatrix);
PrintGraphWeight(Matrix);
}
if (nNumber == 3)
{
Deikstri alg = new Deikstri();
alg.AlgDeikstra(Matrix);
}
if ((nNumber != 2)&&(nNumber!=1)&&(nNumber!=3))
Console.WriteLine("Ошибка");
Console.WriteLine();
Console.WriteLine("\n Введите 0, если хотите выйти из программы, \nВведите 1, если хотите добавить ребро, \nВведите 2, если хотите добавить вершину, \nВведите 3, если хотите запустить алгоритм ещё раз");
nNumber = Convert.ToInt32(Console.ReadLine());
Console.WriteLine();
}
}
public int nQuantitys()
{
Console.WriteLine(" Введите количество вершин:\n");
int nQuantity = Convert.ToInt32(Console.ReadLine());
while(nQuantity==0)
{
Console.WriteLine("\nОшибка! Введите другое количество вершин.\n");
nQuantity = Convert.ToInt32(Console.ReadLine());
}
Console.WriteLine();
return nQuantity;
}
}
}
Класс Deikstri.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Дейкстры
{
class Deikstri:Graph
{
public int p, xn, xk;
public bool[] flag = new bool[100];
public int[] l = new int[100];
public string s;
public string[] path = new string[100];
public int min(int nQuantity)
{
int i, result = 0;
for (i = 0; i < nQuantity; i++)
if (!(flag[i])) result = i;
for (i = 0; i < nQuantity; i++)
if ((l[result] > l[i]) && (!flag[i])) result = i;
return result;
}
public int minim(int x, int y)
{
if (x < y) return x;
return y;
}
public void AlgDeikstra(int[,] Matrix)
{
Console.WriteLine("Задайте начальную точку: ");
xn = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Задайте конечную точку: ");
xk = Convert.ToInt32(Console.ReadLine());
xk--;
xn--;
if (xn == xk)
{
Console.WriteLine("Начальная и конечная точки совпадают.");
Console.ReadKey();
}
for (int i = 0; i < Matrix.GetLength(0); i++)
{
flag[i] = false;
l[i] = 65535;
}
l[xn] = 0;
flag[xn] = true;
p = xn;
s = Convert.ToString(xn + 1);
for (int i = 1; i <= Matrix.GetLength(0); i++)
{
path[i] = "X";
path[i] = path[i] + s;
}
do
{
for (int i = 0; i < Matrix.GetLength(0); i++)
if ((Matrix[p, i] != 65535) && (!flag[i]) && (i != p))
{
if (l[i] > l[p] + Matrix[p, i])
{
s = Convert.ToString(i + 1);
path[i + 1] = path[p + 1];
path[i + 1] = path[i + 1] + "-X";
path[i + 1] = path[i + 1] + s;
}
l[i] = minim(l[i], l[p] + Matrix[p, i]);
}
p = min(Matrix.GetLength(0));
flag[p] = true;
}
while (p != xk);
if (l[p] != 65535)
{
Console.WriteLine("Путь: {0}", path[p + 1]);
Console.WriteLine("Длина пути: {0}", l[p]);
}
else
Console.WriteLine("Путь не существует!");
}
}
}
Класс Program.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Дейкстры
{
class Program
{
static void Main(string[] args)
{
Graph grGraf = new Graph();
Deikstri alAlgor = new Deikstri();
int nQuantity = grGraf.nQuantitys();
int[,] Matrix = new int[nQuantity, nQuantity];
Matrix = grGraf.ReadGraphWeight(nQuantity);
grGraf.PrintGraphWeight(Matrix);
alAlgor.AlgDeikstra(Matrix);
grGraf.End(Matrix);
Console.ReadKey();
}
}
4. ТЕСТИРОВАНИЕ
Вводим граф:
Результат:
|
5. ВЫВОД Был разобран и изучен алгоритм Дейкстры. Была написана реализующая этот алгоритм программа. Также было проведено тестирование, которое не выявило никаких проблем. Программы работает без сбоев и ошибок. 6. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Роберт Седжвик. Фундаментальные алгоритмы на C++. Часть 5 2. http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры |