Реферат: Разработка системы задач (алгоритмы-программы) по дискретной математике

( Текст программы см. Приложение 2)

Диспетчер и милиция. У диспетчера имеется схема города, на которой изображены районы и дороги, связывающие данные районы. На схеме указаны расстояния от одного пункта к другому и направление движения, которое разрешено. Схема выглядит следующим образом:

1

6

2

2

3

4

4

1

3

5

1

1

1

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

Решение. Входные и выходные данные:

Первая строка входного файла содержит количество районов города. Затем идет матрица смежности, где занесены все пути из одной вершины в другую с расстоянием:

6

0 3 7 0 0 0

1 0 2 0 0 1

0 1 0 4 4 0

0 0 0 0 1 5

0 0 1 0 0 3

0 0 0 2 0 0

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

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

Единственное число, которое представляет собой минимальный путь, который предстоит покрыть милицейской машине.

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