4. Укрупнённый алгоритм решения задачи
4.1.
{
Данные = ЧтениеДанных
Граф = ПостроитьГраф(Данные)
Если (Существует(Маршрут(Граф, А. В)))
{
Вывести Маршрут(Граф, А. В)
} иначе {
Пути нет :O
}
}
4.2. Алгоритм нахождения маршрута
{
for (каждая вершина v из V)
{
d[v] ← ∞;
Pr[v] ← -1;
}
d[s] ← 0;
Q ← V[G];
while (Q ≠ 0)
{
u ← Extract-Min(Q);
for (каждая вершина v из Adj[u])
if (d[v] > d[u] + w(u, v))
{
d[v] ← d[u] + w(u, v);
Pr[v] ← u;
}
}
ВывестиМаршрут(A, B, Pr)
}
4.3. Алгоритм вывода маршрута
{
Если (A == B)
{
Вывести(A -> )
} иначе {
Если (Pr[B] == -1)
{
Маршрута нет
} иначе {
ВывестиМаршрут(A, Pr[B], Pr)
Вывести(B -> )
}
}
}
5. Структура программы
Текст программы разбит на три модуля.
Модуль 1 содержит основную подпрограмму, осуществляющую чтение исходных данных, построение графа и выдачу результата.
Модуль 2 содержит подпрограмму поиска и вывода пути.
Модуль 3 содержит основные операции для работы с линейным списком.
5.1. Состав модуля 1:
Главная функция main:
Назначение: чтение исходных данных, построение графа, выдача результата
Прототип: int main()
Функция getCity:
Назначение: получить номер города по имени (возможно, добавив его в массив городов, если город в массиве отсутствует)
Прототип: int getCity(char city[100][100], int *cityN, char cityName[100])
Параметры: city – массив городов, cityN – количество городов (изменяемое), cityName – имя города
5.2. Состав модуля 2:
Функция printMinimalPathway:
Назначение: поиск путей в графе Алгоритмом Дейкстры, вывод минимального пути или сообщения о том, что пути нет
Прототип: void printMinimalPathway(list *G[100], int N, int weights[100][100], char city[100][100], int A, int B)
Параметры: G – список смежности, N – количество вершин, weights – массив весов, city – массив имён городов, A – исходный пункт, B – конечный
5.3. Структура программы по управлению:
6. Текст программы на языке C++
main.cpp
#include <stdio.h>
#include <string.h>
#include "list.h"
#include "graph.h"
int getCity(char city[100][100], int *cityN, char cityName[100])
{
for (int i = 0; i < *cityN; i++)
{
if (!strcmp(city[i], cityName))
{
return i;
}
}
strcpy(city[*cityN], cityName);
int ret = *cityN;
(*cityN)++;
return ret;
}
int main()
{
char filename[16];
printf("Filename: "); gets(filename);
FILE *f = fopen(filename, "r");
if (!f)
{
perror("Error opening file");
return 1;
}
// Создание пустого графа
list *G[100];
int cityN = 0;
char city[100][100];
int weights[100][100];
int N; fscanf(f, "%d", &N);
if (N == 0)
{
printf("No way\n");
return 0;
}
int M; fscanf(f, "%d", &M);
for (int i = 0; i < N; i++)
{
G[i] = new_list();
for (int j = 0; j < N; j++)
{
weights[i][j] = 0;
}
}
// Ввод системы дорог
for (int i = 0; i < M; i++)
{
char temp[100];
fscanf(f, "%s", &temp);
int city1 = getCity(city, &cityN, temp);
fscanf(f, "%s", &temp);
int city2 = getCity(city, &cityN, temp);
int s, p;
fscanf(f, "%d %d", &s, &p);
push(G[city1], city2);
push(G[city2], city1);
if (!weights[city1][city2] || weights[city1][city2] > s + p)
{
weights[city1][city2] = weights[city2][city1] = s + p;
}
}
// Остальные данные
char _A[100], _B[100];
fscanf(f, "%s %s", &_A, &_B);
int A = getCity(city, &cityN, _A);
int B = getCity(city, &cityN, _B);
// Вычисление и вывод результата
printMinimalPathway(G, N, weights, city, A, B);
return 0;
}
graph.h
#pragma once
#include "list.h"
void printMinimalPathway(list *G[100], int N, int weights[100][100], char city[100][100], int A, int B);
graph.cpp
#include <stdio.h>
#include "list.h"
#include "graph.h"
void _printPath(int from, int to, char city[100][100], int Pr[100])
{
if (from == to)
{
printf("%s", city[to]);
} else {
if (Pr[to] == -1)
{
printf("No way\n");
} else {
_printPath(from, Pr[to], city, Pr);
printf(" -> %s", city[to]);
}
}
}
void printMinimalPathway(list *G[100], int N, int weights[100][100], char city[100][100], int A, int B)
{
int d[100], Pr[100];
for (int i = 0; i < N; i++)
{
d[i] = 100000;
Pr[i] = -1;
}
d[A] = 0;
list *Q = new_list();
for (int i = 0; i < N; i++)
{
push(Q, i);
}
while (Q != Q->next)
{
int u = pop(Q, d);
list *cur = G[u];
while (G[u] != (cur = cur->next))
{
int v = cur->data;
if (d[v] > d[u] + weights[u][v])
{
d[v] = d[u] + weights[u][v];
Pr[v] = u;
}
}
}
_printPath(A, B, city, Pr);
}
list.h
#pragma once
struct list
{
list *next;
list *prev;
int data;
};
list *new_list();
int pop(list *, int *);
void push(list *, int);
list.cpp
#include "list.h"
#include <stdio.h>
list *new_list()
{
list *q = new list;
q->data = 0;
q->next = q;
q->prev = q;
return q;
}
int pop(list *q, int *d)
{
if (q->prev == q)
{
printf("Queue was empty\n");
return 0;
}
float min = d[q->prev->data];
list *victim = q->prev;
list *current = q;
while (q != (current = current->next))
{
if (d[current->data] < min)
{
min = d[current->data];
victim = current;
}
}
victim->prev->next = victim->next;
victim->next->prev = victim->prev;
int data = victim->data;
delete victim;
return data;
}
void push(list *q, int data)
{
list *tmp = q->next;
q->next = new list;
q->next->prev = q;
q->next->next = tmp;
q->next->data = data;
tmp->prev = q->next;
}