Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Программа определяет кратчайший путь на графе от заданной начальной точки до конечной.
- GM
- """
- def find_value(l, value):
- result = []
- for i, val in enumerate(l):
- if value == val:
- result.append(i)
- return result
- m_size = int(input("Размер матрицы: "))
- matric = []
- start_point = int(input("Начальная точка: ")) - 1
- end_point = int(input("Конечная точка: ")) - 1
- for i in range(0, m_size):
- converted_string = []
- for num in input("Введите " + str(i + 1) + " срочку матрицы: ").split(" "):
- converted_string.append(int(num))
- matric.append(converted_string)
- edges = [[], []]
- weight = []
- for i_string in range(0, m_size):
- for i_val in range(0, m_size):
- if matric[i_string][i_val] != 0:
- edges[0].append(i_string)
- edges[1].append(i_val)
- weight.append(matric[i_string][i_val])
- point_distance = []
- for i in range(0, m_size):
- point_distance.append(999)
- ways = []
- for i in range(0, m_size):
- ways.append(str(start_point+1))
- point_distance[start_point] = 0
- out_points = []
- while len(out_points) != m_size:
- checking_point = None
- for index_point in range(0, len(point_distance)):
- if checking_point == None and (index_point not in out_points):
- checking_point = index_point
- elif checking_point != None:
- if point_distance[checking_point] > point_distance[index_point] and (index_point not in out_points):
- checking_point = index_point
- for edge_index in find_value(edges[0], checking_point):
- if edges[1][edge_index] not in out_points and point_distance[edges[1][edge_index]] > point_distance[checking_point] + weight[edge_index]:
- point_distance[edges[1][edge_index]] = point_distance[checking_point] + weight[edge_index]
- ways[edges[1][edge_index]] = ways[checking_point] + str(edges[1][edge_index] + 1)
- out_points.append(checking_point)
- print("Расстояние: " + str(point_distance[end_point]))
- print("Путь: " + ways[end_point])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement