کد تبدیل گراف به ماتریس های مجاورت و تلافی به زبان پایتون

Question

گراف یک سری شهر هست هر راس نشان یک شهر و هر یال طول مسیر هستش حالا باید به زبان پایتون یک برنامه بنویسیم که گراف بگیره و با استفاده از ماتریس ها بهینه ترین راه و مسیر های هر شهر به شهر دیگه رو بهمون بگه و همچین بگه ک مثلا از شهر یک به دو فلان اندازه طول می‌کشه و اینکه اگه از یک شهر دیگه مثل شهر سه برای رسیدن به شهر دو استفاده کرده بهمون بگه

Answer 1

در اینجا مثالی از نحوه تبدیل گراف به ماتریس مجاورت و فاصله در پایتون آورده شده است:

import numpy as np
import networkx as nx

# Create a graph
G = nx.Graph()

# Add edges to the graph with their weights (distances)
G.add_edge('City 1', 'City 2', weight=10)
G.add_edge('City 1', 'City 3', weight=20)
G.add_edge('City 2', 'City 4', weight=15)

# Get the number of nodes (cities) in the graph
n = G.number_of_nodes()

# Initialize the adjacency matrix with zeros
adj_matrix = np.zeros((n, n))

# Fill the adjacency matrix with the edges of the graph
for i, j, w in G.edges(data='weight'):
    adj_matrix[i][j] = w
    adj_matrix[j][i] = w

# Initialize the distance matrix with infinity
dist_matrix = np.full((n, n), np.inf)

# Fill the distance matrix with the shortest path distances between every pair of cities
for i in range(n):
    for j in range(n):
        if i != j:
            try:
                dist_matrix[i][j] = nx.shortest_path_length(G, source=i, target=j, weight='weight')
            except:
                dist_matrix[i][j] = float('inf')

print("Adjacency Matrix:\n", adj_matrix)
print("Distance Matrix:\n", dist_matrix)

Translation is too long to be saved

در این مثال، نمودار به عنوان نمونه ای از کلاس networkx.Graph نمایش داده می شود. یال ها با وزن (فاصله ها) با استفاده از روش add_edge به نمودار اضافه می شوند. سپس کد یک ماتریس مجاورت و یک ماتریس فاصله با ابعاد مناسب را بر اساس تعداد گره ها (شهرها) در نمودار مقداردهی اولیه می کند. در نهایت، کد ماتریس مجاورت را با لبه‌های نمودار و ماتریس فاصله را با کوتاه‌ترین فاصله‌های مسیر بین هر جفت شهر پر می‌کند. برای بدست آوردن کوتاه ترین مسیر بین دو گره می توانید از متد shortest_path_length از NetworkX استفاده کنید. همچنین می توانید از سایر الگوریتم های کوتاه ترین مسیر مانند Dijkstra، A* و غیره استفاده کنید.