لحل هذا السؤال، يمكن كتابة دالة بلغة البايثون تستخدم خوارزمية البحث بأولوية العمق (DFS) لإيجاد المسار الأقصر في مخطط غير موزون. الخوارزمية DFS تقوم بالتنقل في الجراف (Graph) عبر الاستمرار في الذهاب عميقًا في الفرع الواحد من العقدة (Node) قبل التحول إلى الفرع الآخر.
الدالة التالية تستخدم خوارزمية DFS لإيجاد المسار الأقصر في مخطط غير موزون:
def dfs_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if start not in graph:
return None
shortest = None
for node in graph[start]:
if node not in path:
new_path = dfs_shortest_path(graph, node, end, path)
if new_path:
if not shortest or len(new_path) < len(shortest):
shortest = new_path
return shortest
# Exmaple usage:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
start_node = 'A'
end_node = 'F'
shortest_path = dfs_shortest_path(graph, start_node, end_node)
print(shortest_path)
تقوم الدالة بتمثيل الجراف باستخدام قاموس (dictionary) حيث يكون كل مفتاح هو عقدة وقيمتها هي العقد الأخرى التي تتصل بها. تبدأ الدالة من العقدة البداية وتقوم بالبحث عن المسار الأقصر إلى العقدة النهائية باستخدام الخوارزمية DFS. تُطبع في النهاية المسار الأقصر الموجود بين العقدتين المحددتين.
