﻿

Лабораторная работа 5 МАПКС. Кратчайший путь

Nov 30th, 2020
735
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. """
2. Программа определяет кратчайший путь на графе от заданной начальной точки до конечной.
3. GM
4. """
5. def find_value(l, value):
6.     result = []
7.     for i, val in enumerate(l):
8.         if value == val:
9.             result.append(i)
10.     return result
11. m_size = int(input("Размер матрицы: "))
12. matric = []
13. start_point = int(input("Начальная точка: ")) - 1
14. end_point = int(input("Конечная точка: ")) - 1
15. for i in range(0, m_size):
16.     converted_string = []
17.     for num in input("Введите " + str(i + 1) + " срочку матрицы: ").split(" "):
18.         converted_string.append(int(num))
19.     matric.append(converted_string)
20. edges = [[], []]
21. weight = []
22. for i_string in range(0, m_size):
23.     for i_val in range(0, m_size):
24.         if matric[i_string][i_val] != 0:
25.             edges[0].append(i_string)
26.             edges[1].append(i_val)
27.             weight.append(matric[i_string][i_val])
28. point_distance = []
29. for i in range(0, m_size):
30.     point_distance.append(999)
31. ways = []
32. for i in range(0, m_size):
33.     ways.append(str(start_point+1))
34. point_distance[start_point] = 0
35. out_points = []
36. while len(out_points) != m_size:
37.     checking_point = None
38.     for index_point in range(0, len(point_distance)):
39.         if checking_point == None and (index_point not in out_points):
40.             checking_point = index_point
41.         elif checking_point != None:
42.             if point_distance[checking_point] > point_distance[index_point] and (index_point not in out_points):
43.                 checking_point = index_point
44.     for edge_index in find_value(edges[0], checking_point):
45.         if edges[1][edge_index] not in out_points and point_distance[edges[1][edge_index]] > point_distance[checking_point] + weight[edge_index]:
46.             point_distance[edges[1][edge_index]] = point_distance[checking_point] + weight[edge_index]
47.             ways[edges[1][edge_index]] = ways[checking_point] + str(edges[1][edge_index] + 1)
48.     out_points.append(checking_point)
49. print("Расстояние: " + str(point_distance[end_point]))
50. print("Путь: " + ways[end_point])
51.
RAW Paste Data