Решение задачи на вычисление количества бензина для проезда между несколькими городами

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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

Курсовая работа

по практикуму на ЭВМ: структуры данных и алгоритмы

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

Группа                                                           ПМ-92

Студент                                                         Чемерилов А.В.

Преподаватель                                              Шапошникова Т.А.

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

1. Условие задачи

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

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

 Во входном файле INPUT.TXT записано сначала число N (1 ≤ N ≤ 100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Далее идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону);

между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

 В выходной файл OUTPUT.TXT выведите одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

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

2.1. Исходные данные задачи: n- количество городов, nÎN, 1≤n≤100,

B- множество значений стоимости бензина, B= {b_i|b_iÎZ, 0≤b_i≤100-стоимость бензина в i-ом городе, i=1,…,n},

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

S- система дорог, S={a_j, c_j|a_j, c_jÎN, 1≤a_j, c_j≤n, a_j≠c_j, a_j- город начала дороги, с_j- город конца дороги, j=1, 2, …,m}

2.2. Результат:  RezÎN U {0}- стоимость проезда, если добраться возможно, -1- если добраться не возможно.

2.3. Решение: Математическая модель системы дорог -  это неориентированный взвешенный несвязный (так как в задаче не говорится, что все города обязательно должны быть связаны дорогами) граф G=(V, E) с весовой функцией w:E→Z, причем w(u, v)≥0 и вес всех ребер исходящих из одной вершины u будет одинаковым для всех (u, v) ÎE.

 Взвешенным графом назовем пару (G, w) для которой выполняется следующее:

пусть G – граф, w: E_G→R+ вещественнозначная функция, ставящая в соответствие каждому ребру eнеотрицательное число w(e) – вес ребра e.

 В данной задаче вершины соответствуют городам, а дуги - дорогам. Дуга (u,v) ведет из вершины u в вершину v, где u- это вершина, соответствующая городу-началу дороги, а v- вершина, соответствующая городу- концу дороги. Вес дуги (u, v)  равносилен количеству затраченных денег на бензин, необходимых для того чтобы проехать из города u в город v. Вес ребра (u,x) для любой вершины x смежной с вершиной u одинаковый, то есть w(u,x₁)=w(u,x₂)=…=w(u,x_q),

где q-количество смежных вершин для вершины u.

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

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

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

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

В неориентированном взвешенным несвязном графе определить самый дешевый путь из первого города в последний.

 Самый дешевый путь из первого города в последний это тот, который образуют дуги, сумма весов которых минимальна, по сравнению с суммой весов дуг, образующих любой другой маршрут в последний город из первого.

 Если количество городов равно 1, то ехать никуда не надо. Если множество городов  больше 1 и есть прямая дорога из первого города в последний, то результатом будет являться стоимость бензина в первом городе. Если множество городов  больше 1 и не существует прямой дороги из первого города в последний, то воспользуемся следующим алгоритмом решения:

 Если доехать можно, то  t=1 и a= первый возможный маршрут и

пока не перебрал все  другие, отличные от a, маршруты b

                                         повторять

                                                   если a>=b, то a=b

 Если t=1 то, result=a, иначе result=-1

 Для нахождения кратчайшего пути будем использовать алгоритм Дейкстры.           Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного неориентированного графа G(V, E) с исходной вершиной s (в моем случае s=1), в котором веса всех ребер неотрицательны (w(u, v)≥0 для всех (u, v) Î E).

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

 1) Поиск самого дешевого пути от первого города до последнего

 2) Ввод системы дорог

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

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

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

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

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

<список – цен>::= пробел | пробел <цена> <список – цен>