dist_matrix[i][j] = min(dist_matrix[i][j], dist_matrix[i][k] + dist_matrix[k][j]) return dist_matrix def find_shortest_path(graph, start, end) if graph[start][end] == graph[start][i] + graph[i][end]: path.insert(0, i) end = i break return path if graph[i][j] != 0 and graph[i][j] != float(inf): G.add_edge(i+1, j+1, weight=graph[i][j]) pos = nx.spring_layout(G) edges = [(path[i]+1, path[i+1]+1) for i in range(len(path)-1)] nx.draw_networkx_edges(G, pos, edgelist=edges, edge_color=r, width=2) [0, 9, 0, 0, 6, 2], [9, 0, 7, 0, 0, 5], [0, 7, 0, 3, 0, 0], [0, 0, 3, 0, 8, 4], [6, 0, 0, 8, 0, 0], [2, 5, 0, 4, 0, 0] |
Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filialiBog'liq 5-amaliyBu sahifa navigatsiya:
- dist_matrix[i][j] = min(dist_matrix[i][j], dist_matrix[i][k] + dist_matrix[k][j]) return dist_matrix def find_shortest_path(graph, start, end)
- if graph[start][end] == graph[start][i] + graph[i][end]: path.insert(0, i) end = i break return path
- if graph[i][j] != 0 and graph[i][j] != float(inf): G.add_edge(i+1, j+1, weight=graph[i][j]) pos = nx.spring_layout(G)
- edges = [(path[i]+1, path[i+1]+1) for i in range(len(path)-1)] nx.draw_networkx_edges(G, pos, edgelist=edges, edge_color=r, width=2)
- [0, 9, 0, 0, 6, 2], [9, 0, 7, 0, 0, 5], [0, 7, 0, 3, 0, 0], [0, 0, 3, 0, 8, 4], [6, 0, 0, 8, 0, 0], [2, 5, 0, 4, 0, 0]
Python:
import networkx as nx
import matplotlib.pyplot as plt
def floyd_warshall(graph):
n = len(graph)
dist_matrix = [row[:] for row in graph]
for k in range(n):
for i in range(n):
for j in range(n):
dist_matrix[i][j] = min(dist_matrix[i][j], dist_matrix[i][k] + dist_matrix[k][j])
return dist_matrix
def find_shortest_path(graph, start, end):
path = [end]
while end != start:
for i in range(len(graph)):
if graph[start][end] == graph[start][i] + graph[i][end]:
path.insert(0, i)
end = i
break
return path
def draw_graph(graph, path=None):
G = nx.Graph()
for i in range(len(graph)):
for j in range(len(graph[0])):
if graph[i][j] != 0 and graph[i][j] != float('inf'):
G.add_edge(i+1, j+1, weight=graph[i][j])
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, font_weight='bold', node_size=700,
node_color="skyblue", font_size=10, font_color="black")
if path:
edges = [(path[i]+1, path[i+1]+1) for i in range(len(path)-1)]
nx.draw_networkx_edges(G, pos, edgelist=edges, edge_color='r', width=2)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.show()
# Berilgan matris
graph = [
[0, 9, 0, 0, 6, 2],
[9, 0, 7, 0, 0, 5],
[0, 7, 0, 3, 0, 0],
[0, 0, 3, 0, 8, 4],
[6, 0, 0, 8, 0, 0],
[2, 5, 0, 4, 0, 0]
]
# Algoritmani ishga tushiramiz
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali
|
