Нужна помощь в отладке патчей Флойда-Уоршалла с определенными условиями графа ⇐ Python

[Anonymous]

Я работаю над этой проблемой уже несколько дней и не добился никакого прогресса. Я не смог добиться никакого прогресса и был бы самым счастливым человеком на свете, если бы мне дали совет о том, как двигаться вперед или даже о решении этой проблемы.
Я дал проблема здесь и моя текущая попытка решения ниже:
Проблема. Это неправильная реализация Floyd-Warshall.

Код: Выделить всё

floyd_warshall(dist, n):
# Assume dist[i][j] is positive infinity if there is no edge between them
for i ranging from 1 to n:
for j ranging from 1 to n:
for k ranging from 1 to n:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Вот попытка исправить это.

Код: Выделить всё

floyd_warshall_patch1(dist, n, k):
# dist[i][i] is zero
# dist[i][j] is otherwise the weighted of the directed edge from i to j if it exists
# dist[i][j] is otherwise positive infinity
for i ranging from 1 to k:
floyd_warshall(dist, n)

Вот еще одна попытка исправить это.

Код: Выделить всё

floyd_warshall_patch2(dist, n)
# dist[i][i] is zero
# dist[i][j] is otherwise the weighted of the directed edge from i to j if it exists
# dist[i][j] is otherwise positive infinity
for i ranging from 1 to n:
for j ranging from 1 to n:
for k ranging from 1 to n:
dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

Ваша задача — построить ориентированный граф с N вершинами и M ребрами так, чтобы при заданном параметре K выходные данные floyd_warshall_patch1 совпадали с выходными данными floyd_warshall_patch2 на данном графе, но вывод floyd_warshall_patch1, когда задан K-1, не работает.
Дополнительные ограничения - (https://i.sstatic.net/gw1gVpkI.png)
Мое решение -

Код: Выделить всё

def floyd_warshall_patch1(dist, n, k):
for i in range(k):
dist[i][i] = 0
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

def floyd_warshall_patch2(dist, n):
for i in range(n):
dist[i][i] = 0
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

def create_graph(N, M, K):

if K >= N or K == N - 1 or M < N - 1:
return "NO", []

edges = []
# Create a path from 1 to N
for i in range(1, N):
edges.append((i, i + 1, 1))

# Add a back edge to form a cycle
if M > N - 1:
edges.append((N, 1, 10))  # Adding a cycle with a reasonable weight

# Optionally add more complexity with additional edges
additional_edges = M - len(edges)
while additional_edges > 0:
from_node = additional_edges % N + 1
to_node = (additional_edges * 2) % N + 1
if from_node != to_node:
edges.append((from_node, to_node, additional_edges + 5))  # Randomized weight for complexity
additional_edges -= 1

return "YES", edges

N, M, K = map(int, input().split())

result, edges = create_graph(N, M, K)

print(result)
if result == "YES":
for edge in edges:
print(" ".join(map(str, edge)))

Я просто понятия не имею, что делать.

Подробнее здесь: https://stackoverflow.com/questions/783 ... conditions