6 практика

СОДЕРЖАНИЕ:

1Введение……………………………………………………………...………….3

2Ход работы………………………………………………………………………4

2.1Инициализация графа и заполнение его весами……...………………...4

2.2Выбор пунктов для нахождения кратчайшего пути……………………4

3Заключение…………………………………………………………………..…..5

Приложение А…………………………………………………………………..…6

2

1 Введение

Целью работы является реализовать возможность работы с графом N

узлов, M ребер. Выберете самостоятельно структуру. Обеспечьте следующие интерфейсные методы:

ввод графа (можно случайным образом, можно вводить с клавиатуры)

НЕДОПУСТИМО работать только с конечным числом ребер и узлов.

Приложение должно позволять вводить разные графы.

вывод графа - матрица смежности или весов.

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

3

2Ход работы

2.1Инициализация графа и заполнение его весами

На рисунке 2.1 представлена инициализация графа и заполнения его случайными элементами из массива mas.

Рисунок 2.1 – Инициализация графа и его заполнение

2.2 Выбор пунктов для нахождения кратчайшего пути

На рисунке 2.2 представлен выбор пунктов для поиска кратчайшего пути и вывод кратчайшего пути через смежную матрицу.

Рисунок 2.2 – Вывод кратчайшего пути от А до В

4

3Заключение

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

Наиболее затруднительным было создание и инициализация графа.

Отчет был составлен согласно ОС ТУСУР 2021.

5

Приложение А

(обязательное)

Программа для работы с графами и поиска кратчайшего пути

import random

print("Введите количество узлов") N = int(input())

a = ((N ** 2) - N) // 2

print("Введите число рёбер от", N - 1, "до", a) M = int(input())

count = 0 mas = []

for l in range(0, 100000): # Создание списка с расстоянием дорог count += 1

x1 = random.randint(1, 100) mas.append(x1)

if count == M: break

a = [[0] * N for i in range(N)] # Создание матрицы дорог и заполнение главной диагонали

for i in range(N):

for j in range(N): if i == j:

a[i][j] = 0 else:

a[i][j] = -1

l = 0

for x in range(N): # Заполнение матрицы длинной дорог for y in range(N):

for v in range(10 ** 100):

irand = (random.randint(1, 1000000)) % N jrand = (random.randint(1, 1000000)) % N if a[irand][jrand] == -1:

a[irand][jrand] = mas[l] a[jrand][irand] = mas[l] l += 1

if l == M: break

else: continue

break break

for row in a:

print(' '.join([str(elem) for elem in row]))

print("Введите пункт отправки") A = int(input())

print("Введите пункт назначения") B = int(input())

for k in range(0, N, 1):

for d in range(0, N, 1):

for g in range(0, N, 1):

if a[d][g] > a[d][k] + a[k][g]: a[d][g] = a[d][k] + a[k][g]

6

print("Кратчайший путь из пунка А в пункт В") print(a[A - 1][B - 1])

7