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

Новосибирский Государственный Технический Университет

Кафедра прикладной математики

Курсовая работа по практикуму на ЭВМ:

структуры данных и алгоритмы

Факультет: прикладной математики и информатики

Группа:

Студент:

Преподаватели:

Новосибирск 2009

1. Условие

В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города A в город B с минимальной величиной S + P, где S – сумма длин дорог пути, а P – сумма пошлин проезжаемых дорог.

2. Анализ задачи

2.1. Исходные данные задачи:

n – количество городов,

m – количество дорог,

G – список дорог,

A – исходный город,

B – конечный город,

2.2. Результат:

- маршрут из A в B с минимальной величиной S + P; “No Way”, если маршрута нет

2.3. Решение:

Математическая модель системы двусторонних дорог – неориентированный взвешенный помеченный граф с весовой функцией , причём . При этом вершины соответствуют городам (метка вершины – название города), а рёбра – двусторонним дорогам. Вес ребра определяется по формуле , где - длина дороги между городами u и v, - пошлина, взимаемая за проезд по этой дороге. В случае существования нескольких дорог между одной и той же парой городов, в граф добавляется ребро с наименьшим весом (поскольку задача состоит в отыскании пути с наименьшим весом).

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

Основные подзадачи:

1. Ввод системы дорог

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

Формальная постановка задачи

Построить граф заданной системы дорог, найти кратчайший путь между двумя заданными вершинами.

Основные подзадачи:

1. Ввод системы дорог

2) Нахождение кратчайшего пути

3. Структуры данных, используемые для представления исходных данных и результатов задачи

3.1. Входные данные

Внешнее представление системы двусторонних дорог:

<система-дорог> ::= <количество-городов> <количество-дорог> <список-дорог>

<количество-городов> ::= <натуральное-число>

<количество-дорог> ::= <натуральное-число>

<название-города> ::= <буква>|<название-города> <буква>

<список-дорог> ::= <дорога>|<дорога> <список-дорог>

<дорога> ::= <название-города> <название-города> <расстояние> <пошлина>

<расстояние> ::= <натуральное-число>

<пошлина> ::= <натуральное-число>

Внутреннее представление системы двусторонних дорог:

Для алгоритма Дейкстры хорошим представлением графа является представление списками смежности. Список смежности даёт компактное представление для разреженных графов – тех, у которых множество рёбер много меньше множества вершин, что характерно для системы дорог. Чтобы не усложнять списки смежности, вместо названия города будем помечать вершину номером. Вершины пронумеруем с нуля. Список смежных вершин представим двусвязным закольцованным списком (такой список можно так же использовать в качестве очереди, требуемой для алгоритма Дейкстры).

list *G[100]; // Список смежности вершин

char city[100][100]; // Массив городов

3.2. Выходные данные

Внешнее представление: список вершин маршрута или текстовое сообщение «Пути нет»

Внутреннее представление:

Pr[] – массив предшественников вершин;