Отчет 6

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра ВМиК

Отчёт

по лабораторной работе

«Нахождение кратчайших путей в графе.

Алгоритм Дейкстры»

Выполнила: студ. гр. МО-204

Валиева Э.А.

Проверила:

Верхотурова Г.Н.

Уфа - 2014

Постановка задачи:

Написать программу, осуществляющую нахождение кратчайшего пути между двумя фиксированными вершинами заданного графа с помощью алгоритма Дейкстры

Входные и выходные данные:

textBox1.Text-Задаем начальную вершину

textBox2.Text-Задаем конечную вершину

matr-Матрица весов

bool[] x = new bool[V]; //Массив,пройденных вершин

x[i]=false - еще не найден кратчайший путь в i-ю вершину,

x[i]=true - кратчайший путь в i-ю вершину уже найден

int[] h = new int[V];//Массив, вершин на кратчайшем пути

h[i] - вершина, предшествующая i-й вершине на кратчайшем пути

int[] t = new int[V];//Массив содержащий длины кратчайших путей

Алгоритм:

1. Приписываем вершине st постоянную метку, равную нулю, а всем остальным вершинам, отличным от st, временные метки, равные бесконечности. Положим v=st, где v-последняя из вершин, получивших постоянную метку.

2. Для всех смежных u с v и не имеющим постоянной метки, пересчитываем величины:

t(u)=min{d(u),d(v)+matr(v,u)} (1)

1. Если t(u)=∞ для всех непомеченных вершин u, закончить процедуру алгоритма: «Нет пути».

2. Иначе, переходим к 3 шагу.

3. Выбрать ту из вершин u, которая имеет наименьшую временную метку, т.е. ту, для которой величина t(u) является наименьшей.

4. Положим v=u-вершина графа, с наименьшей временной меткой, которой присваивается постоянная метка.

5. Если v=fin, закончить процедуру. Кратчайший путь из вершины st в fin найден. Это единственный путь из st в fin, составленный из помеченных дуг.

6. Если v≠fin, перейти к шагу 2.

Реализация:

private void button2_Click(object sender, EventArgs e)

{

int N = dataGridView1.RowCount - 1;

int start = Convert.ToInt32(textBox1.Text);

int finish = Convert.ToInt32(textBox2.Text);

int[,] matrix = new int[N, N];

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

{

if (this.dataGridView1.Rows[i].Cells[j].Value == null)

matrix[i, j] = 0;

else

matrix[i, j] = Convert.ToInt32(dataGridView1.Rows[i].Cells[j].Value);

}

Deikstra(matrix, start - 1, finish - 1);

}

void Deikstra(int[,] matrix, int st, int fin)

{

int V = dataGridView1.RowCount - 1;

bool[] x = new bool[V];

int[] h = new int[V];

int[] t = new int[V];

int u;

for (u = 0; u < V; u++)

{

t[u] = 100000;

x[u] = false;

}

h[st] = 0;

t[st] = 0;

x[st] = true;

v = st;

while (true)

{

for (u = 0; u < V; u++)

{

if (matrix[v, u] == 0)

continue;

if (x[u] == false && t[u] > t[v] + matrix[v, u])

{

t[u] = t[v] + matrix[v, u];

h[u] = v;

}

int w = 100000;

v = -1;

for (u = 0; u < V; u++)

{

if (x[u] == false && t[u] < w)

{

v = u;

w = t[u];

}

}

if (v == -1)

{

richTextBox1.Text = richTextBox1.Text + "Нет пути";

break;

}

if (v == fin)

{

{

u = fin;

while (u != st)

{

label5.Text = label5.Text + Convert.ToInt32(u + 1) + " ";

u = h[u];

}

richTextBox1.Text = richTextBox1.Text + Convert.ToInt32(t[fin]) + " ";

break;

}

}

x[v] = true;

}

textBox4.Text = textBox4.Text + label5.Text + Convert.ToInt32(st + 1);

}

Оценка сложности: О(N²)

Вывод:

В ходе лабораторной работы я научилась использовать алгоритм Дейкстры, находить путь между двумя вершинами.