انتخاب مسیر کم‌هزینه با پایتون؛ قرارداد Dijkstra و مرجع مستقل

هنگام بازبینی تغییرات یک تابعِ انتخاب مسیر، دیدنِ نام Dijkstra یا استفاده از صف اولویت کافی نیست. باید روشن باشد «بهترین» یعنی چه، هزینه چگونه جمع می‌شود و جوابِ ناموجود چه شکلی دارد. این آموزش با یک گراف کاملاً ساختگی، پاسخ دستی و مرجع مستقل نشان می‌دهد چه شواهدی برای پذیرش همین قرارداد لازم داریم. هیچ مسیری روی شبکه تنظیم نمی‌شود و عددهای میلی‌ثانیه، تأخیر اندازه‌گیری‌شده نیستند.

۱. کمترین تعداد لینک با کمترین هزینه فرق دارد

فرض کنیم گره‌های A تا E ایستگاه‌های انتزاعیِ یک زنجیرهٔ پردازش باشند. وزن هر لینک، هزینهٔ ثابت و فرضیِ عبور از آن با واحد میلی‌ثانیه است. هزینهٔ مسیر را جمع وزن لینک‌ها تعریف می‌کنیم؛ زمان انتظار، هم‌پوشانیِ پردازش، ازدحام و تغییر هزینه در طول اجرا در این مدل وجود ندارند. بنابراین جمع‌پذیری یک فرض ورودی است، نه نتیجهٔ اندازه‌گیری.

در گراف نمونه، مسیر A، D، E فقط دو لینک دارد، اما هزینه‌اش نه به‌علاوهٔ یک، یعنی ده میلی‌ثانیه است. مسیر A، C، B، D، E چهار لینک دارد و هزینه‌اش یک، دو، یک و یک، در مجموع پنج میلی‌ثانیه می‌شود. انتخاب تعداد لینک کمتر، این پاسخ کم‌هزینه‌تر را از دست می‌دهد. تغییر نام متغیر hop_count به cost نیز چنین خطایی را اصلاح نمی‌کند.

پول و مک‌ورث، در بخش جست‌وجوی کم‌هزینهٔ کتاب خود، تفاوت تعداد یال و مجموع هزینه را توضیح می‌دهند. معیار انتخاب در این درس هزینهٔ انباشته است. گره Z نیز عمداً جدا تعریف شده تا «گرهٔ معتبر ولی دست‌نیافتنی» را با «شناسهٔ ناشناخته» اشتباه نگیریم؛ اولی جواب None دارد و دومی خطای قرارداد است.

۲. گراف جهتدار و قرارداد وزن مثبت

ورودی باید dict واقعی با یک تا هشت گره باشد. نام هر گره رشته‌ای با الگوی [A-Z][A-Z0-9]{0,7} است و همسایه‌های هر گره در dict دیگری قرار می‌گیرند. هر مقصد باید از ابتدا در گراف تعریف شده باشد. این نمایش برای هر زوجِ مرتب حداکثر یک یال دارد؛ چند لینک موازی را با یک نامِ مقصد نمی‌توان نمایش داد.

هر وزن دقیقاً int و در بازهٔ بستهٔ یک تا هزار میلی‌ثانیه است. bool، شناور، صفر، عدد منفی، NaN و بی‌نهایت پذیرفته نمی‌شوند. آرگومان unit نیز فقط رشتهٔ ms را می‌پذیرد و تبدیل واحد انجام نمی‌دهد. صحیح‌بودنِ حساب در این دامنه مانع خطای گردکردنِ جمع‌ها می‌شود، اما دقت فیزیکیِ یک مسیر واقعی را ثابت نمی‌کند.

درس کوتاه‌ترین مسیرِ سجویک و وین در پرینستون، جهت یال، دسترسی‌پذیری و شرط وزن نامنفی برای صورت معمول Dijkstra را شرح می‌دهد. قرارداد ما عمداً سخت‌گیرانه‌تر و فقط مثبت است. یال A به B، وجود B به A را نتیجه نمی‌دهد؛ در همین نمونه از E به A مسیری نداریم. خودحلقه و چرخهٔ مثبت مجازند، ولی دورزدن در آن‌ها هزینهٔ جواب را کاهش نمی‌دهد.

۳. کد کامل و سیاست تساوی مسیرها

فایل dijkstra_route_contract.py با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. best برای هر گره بهترین جفتِ شناخته‌شدهٔ «هزینه، مسیر کامل» را نگه می‌دارد. frontier توده‌ای از همین جفت‌هاست. هنگام خروج یک ورودی، اگر با best فعلی برابر نباشد، کنار گذاشته می‌شود؛ ممکن است پس از یافتن مسیر ارزان‌تر، نسخهٔ قبلی هنوز داخل توده باشد.

مستندات heapq رفتار heappush، heappop و دشواری تغییر اولویتِ ورودی موجود را توضیح می‌دهد. این کد مقدار قدیمی را درجا دست‌کاری نمی‌کند. همسایه با هزینهٔ جمع‌شده و مسیرِ افزوده‌شده پیشنهاد می‌شود؛ فقط پیشنهاد بهتر وارد best و توده می‌شود. آزمون مقصد پس از برداشتن ورودی معتبر انجام می‌شود، نه هنگام نخستین مشاهدهٔ نام مقصد.

برای دو مسیر با هزینهٔ برابر، کوچک‌ترین tuple نام‌های مسیر را در ترتیب واژه‌نامه‌ای پایتون انتخاب می‌کنیم؛ قرارداد مقایسهٔ دنباله‌ها پشتوانهٔ این مقایسه است. در گراف تساوی، هر دو مسیر S، A، T و S، B، T هزینهٔ سه دارند و اولی انتخاب می‌شود؛ حتی اگر B زودتر در dict نوشته شده باشد. این سیاستِ صریحِ همین تابع است، نه شرط ذاتیِ همهٔ پیاده‌سازی‌های Dijkstra.

"""Small directed positive-cost graph; synthetic millisecond costs, no network."""
import heapq
import itertools
import json
import platform
import re


def validate_graph(graph, source, target, unit):
    if type(unit) is not str or unit != "ms":
        raise ValueError("cost unit must be exactly ms")
    if type(graph) is not dict or not 1 <= len(graph) <= 8:
        raise ValueError("graph must be a dict with 1..8 declared nodes")
    if any(type(n) is not str or not re.fullmatch(r"[A-Z][A-Z0-9]{0,7}", n)
           for n in graph):
        raise ValueError("node names must follow the bounded ASCII profile")
    if type(source) is not str or type(target) is not str:
        raise TypeError("source and target must be strings")
    if source not in graph or target not in graph:
        raise ValueError("source and target must be declared")
    for edges in graph.values():
        if type(edges) is not dict:
            raise TypeError("adjacency must be a dict")
        for node, weight in edges.items():
            if type(node) is not str or node not in graph:
                raise ValueError("edge destination must be declared")
            if type(weight) is not int:
                raise TypeError("weights must be exact integers, not bool")
            if not 1 <= weight <= 1000:
                raise ValueError("positive edge costs must be 1..1000 ms")


def shortest_route(graph, source, target, *, unit="ms"):
    validate_graph(graph, source, target, unit)
    best = {source: (0, (source,))}
    frontier = [(0, (source,))]
    while frontier:
        cost, path = heapq.heappop(frontier)
        node = path[-1]
        if best.get(node) != (cost, path):
            continue  # Superseded entry remains physically in the heap.
        if node == target:
            return cost, path
        for neighbor, weight in graph[node].items():
            candidate = (cost + weight, path + (neighbor,))
            if neighbor not in best or candidate < best[neighbor]:
                best[neighbor] = candidate
                heapq.heappush(frontier, candidate)
    return None


def exhaustive_reference(graph, source, target):
    """Independent permutations of intermediate vertices: no heap/relaxation."""
    choices = []
    if source == target:
        return 0, (source,)
    middle = [n for n in graph if n not in (source, target)]
    for count in range(len(middle) + 1):
        for sequence in itertools.permutations(middle, count):
            path = (source,) + sequence + (target,)
            if all(b in graph[a] for a, b in zip(path, path[1:])):
                choices.append((sum(graph[a][b] for a, b in zip(path, path[1:])), path))
    return min(choices) if choices else None


def rejects(exception, function, *args, **kwargs):
    try:
        function(*args, **kwargs)
    except exception:
        return True
    return False


def run_example():
    graph = {"A": {"B": 4, "C": 1, "D": 9},
             "B": {"D": 1, "E": 5}, "C": {"B": 2, "D": 5},
             "D": {"E": 1}, "E": {}, "Z": {}}
    checks = {}
    result = shortest_route(graph, "A", "E")
    checks["hand_four_edges_cost_five"] = result == (5, ("A", "C", "B", "D", "E"))
    checks["fewer_edges_can_cost_more"] = graph["A"]["D"] + graph["D"]["E"] == 10 > result[0]
    checks["source_equals_target_empty_edge_path"] = shortest_route(graph, "C", "C") == (0, ("C",))
    checks["unreachable_declared_node"] = shortest_route(graph, "A", "Z") is None
    checks["directed_not_implicitly_bidirectional"] = shortest_route(graph, "E", "A") is None
    tie = {"S": {"B": 1, "A": 1}, "B": {"T": 2}, "A": {"T": 2}, "T": {}}
    checks["equal_cost_uses_full_lexicographic_path"] = shortest_route(tie, "S", "T") == (3, ("S", "A", "T"))
    reversed_graph = {n: dict(reversed(list(e.items()))) for n, e in reversed(list(tie.items()))}
    checks["tie_not_dict_insertion_order"] = shortest_route(reversed_graph, "S", "T") == shortest_route(tie, "S", "T")
    cycle = {"A": {"B": 1, "T": 5}, "B": {"A": 1, "B": 1, "T": 1}, "T": {}}
    checks["positive_cycle_and_self_loop_do_not_improve"] = shortest_route(cycle, "A", "T") == (2, ("A", "B", "T"))
    stale = {"A": {"B": 9, "C": 1}, "B": {}, "C": {"B": 1}, "Z": {}}
    checks["superseded_heap_entry_exhaustion"] = (
        shortest_route(stale, "A", "B") == (2, ("A", "C", "B")) and
        shortest_route(stale, "A", "Z") is None)
    all_pairs = [(g, a, b) for g in (graph, tie, cycle, stale)
                 for a in g for b in g]
    checks["all_simple_paths_independent_77_queries_one_group"] = all(
        shortest_route(g, a, b) == exhaustive_reference(g, a, b)
        for g, a, b in all_pairs)
    original = json.dumps(graph, sort_keys=True)
    shortest_route(graph, "A", "E")
    checks["input_graph_not_mutated"] = json.dumps(graph, sort_keys=True) == original
    checks["cost_scaling_preserves_chosen_path"] = shortest_route(
        {n: {v: 3 * w for v, w in e.items()} for n, e in graph.items()}, "A", "E") == (15, result[1])
    checks["unknown_endpoint_and_destination_rejected"] = (
        rejects(ValueError, shortest_route, graph, "MISSING", "E") and
        rejects(ValueError, shortest_route, {"A": {"B": 1}}, "A", "A"))
    checks["zero_negative_fraction_bool_nonfinite_weights_rejected"] = all(
        rejects(TypeError if type(w) is not int else ValueError,
                shortest_route, {"A": {"B": w}, "B": {}}, "A", "B")
        for w in (0, -1, 1001, 1.5, True, float("nan"), float("inf")))
    checks["name_shape_and_adjacency_profile_rejected"] = (
        rejects(ValueError, shortest_route, {}, "A", "A") and
        rejects(ValueError, shortest_route, {"a": {}}, "a", "a") and
        rejects(TypeError, shortest_route, {"A": []}, "A", "A") and
        rejects(ValueError, shortest_route, {str(i): {} for i in range(9)}, "0", "0"))
    checks["exact_units_and_integer_closed_bounds"] = (
        rejects(ValueError, shortest_route, graph, "A", "E", unit="s") and
        shortest_route({"A": {"B": 1000}, "B": {}}, "A", "B") == (1000, ("A", "B")) and
        shortest_route({"A": {}}, "A", "A") == (0, ("A",)))
    assert all(type(v) is bool and v for v in checks.values()), checks
    return {"python_version": platform.python_version(),
            "data_origin": "original finite directed graph, hypothetical positive integer costs",
            "cost_unit": "ms (assumed additive costs, not measured latency)",
            "graph": graph, "hand_route_cost_ms": result[0], "hand_route_nodes": result[1],
            "two_edge_alternative_cost_ms": 10,
            "tie_route": shortest_route(tie, "S", "T"),
            "oracle_query_count_in_one_group": len(all_pairs),
            "oracle_strategy": "all permutations of subsets of intermediate vertices; choose min(cost, full_path)",
            "checks": checks, "unique_check_groups": len(checks)}


if __name__ == "__main__":
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

در زمان‌بند قطعی رویداد حسگر، تساوی زمان با ترتیب ورود شکسته می‌شد. اینجا مسیرِ واژه‌نامه‌ای معیار دوم است؛ انتقالِ بی‌فکرِ token زمان‌بند، قرارداد دیگری می‌سازد. ذخیره و کپیِ مسیر کامل نیز هزینه دارد. این مثال هشت‌گرهی، سنجش سرعت یا ادعای پیچیدگیِ دقیقِ یک پیاده‌سازیِ بزرگ با آرایهٔ والد نیست.

۴. مرجع همهٔ مسیرهای ساده و نتیجهٔ اجرا

تابع exhaustive_reference از توده، best یا بهبود مرحله‌ای استفاده نمی‌کند. زیرمجموعه‌های مرتبِ گره‌های میانی را با جایگشت می‌سازد، وجود مستقیمِ تک‌تک یال‌ها را می‌سنجد و مجموع هزینه را حساب می‌کند. از میان مسیرهای موجود، کمترین جفتِ هزینه و مسیر را برمی‌گزیند. چون وزن‌ها مثبت‌اند، حذف چرخه هزینه را کم می‌کند؛ پس بررسی مسیرهای ساده برای یافتن کمینهٔ همین گراف محدود کافی است.

مرجع برای چهار گراف نمونه و تمام زوج‌های مبدأ و مقصد اجرا شد: سی‌وشش، شانزده، نه و شانزده پرس‌وجو؛ جمعاً هفتادوهفت مورد در یک گروه. تمام خروجی‌ها با تابع اصلی برابر بودند. این شمار، همهٔ گراف‌های ممکنِ هشت‌گرهی یا اثبات صوریِ برنامه نیست. استقلالِ روشِ پیمایش احتمالِ تکرار خطای الگوریتم اصلی را کم می‌کند، ولی هر دو تابع همچنان بر تعریف مشترک هزینه و سیاست تساوی تکیه دارند.

خروجی دستی پنج میلی‌ثانیه و مسیر A، C، B، D، E است. شانزده گروهِ معنادارِ بررسی همگی True شدند؛ هفتادوهفت پرس‌وجوی مرجع را دوباره به این عدد اضافه نمی‌کنیم. گروه‌ها شامل جهت، تساوی، چرخه، ورودی قدیمیِ توده، ورودی نامعتبر و عدم تغییر گراف‌اند. ضرب همهٔ وزن‌های نمونه در سه، هزینه را پانزده می‌کند و مسیر انتخابی ثابت می‌ماند؛ این بررسی فقط با وزن‌های همچنان داخل دامنه اجرا شده است.

{
  "python_version": "3.14.5",
  "data_origin": "original finite directed graph, hypothetical positive integer costs",
  "cost_unit": "ms (assumed additive costs, not measured latency)",
  "graph": {
    "A": {
      "B": 4,
      "C": 1,
      "D": 9
    },
    "B": {
      "D": 1,
      "E": 5
    },
    "C": {
      "B": 2,
      "D": 5
    },
    "D": {
      "E": 1
    },
    "E": {},
    "Z": {}
  },
  "hand_route_cost_ms": 5,
  "hand_route_nodes": [
    "A",
    "C",
    "B",
    "D",
    "E"
  ],
  "two_edge_alternative_cost_ms": 10,
  "tie_route": [
    3,
    [
      "S",
      "A",
      "T"
    ]
  ],
  "oracle_query_count_in_one_group": 77,
  "oracle_strategy": "all permutations of subsets of intermediate vertices; choose min(cost, full_path)",
  "checks": {
    "hand_four_edges_cost_five": true,
    "fewer_edges_can_cost_more": true,
    "source_equals_target_empty_edge_path": true,
    "unreachable_declared_node": true,
    "directed_not_implicitly_bidirectional": true,
    "equal_cost_uses_full_lexicographic_path": true,
    "tie_not_dict_insertion_order": true,
    "positive_cycle_and_self_loop_do_not_improve": true,
    "superseded_heap_entry_exhaustion": true,
    "all_simple_paths_independent_77_queries_one_group": true,
    "input_graph_not_mutated": true,
    "cost_scaling_preserves_chosen_path": true,
    "unknown_endpoint_and_destination_rejected": true,
    "zero_negative_fraction_bool_nonfinite_weights_rejected": true,
    "name_shape_and_adjacency_profile_rejected": true,
    "exact_units_and_integer_closed_bounds": true
  },
  "unique_check_groups": 16
}

مرجع جایگشت برای اندازهٔ کوچک مناسب است و رشد آن مانع استفادهٔ بی‌حد می‌شود. در بازبینی تغییر، نخست باید اختلافِ خروجی را با کوچک‌ترین شاهدِ معتبر توضیح داد. همان‌طور که در بررسی ادغام متن و اعتبار تنظیمات دیدیم، پذیرفته‌شدن شکل فایل، رفتار درست را تضمین نمی‌کند؛ اینجا نیز وجود یک tuple خروجی، بدون بررسی یال‌ها و هزینه، کافی نیست.

۵. چهار پرسش با پاسخ کامل

پرسش اول: چرا بازگشتِ فوری با دیدن D از A نادرست است؟ پاسخ: پیشنهاد مستقیم A به D هزینهٔ نه دارد، ولی A، C، B، D هزینهٔ چهار دارد. مقصد باید از توده با بهترین ورودیِ معتبر برداشته شود؛ ساخته‌شدن نخستین پیشنهاد، پایان جست‌وجو نیست.

پرسش دوم: اگر مبدأ و مقصد هر دو C باشند، جواب چیست؟ پاسخ: هزینهٔ صفر و مسیر تک‌گرهی C. هیچ یالی پیموده نمی‌شود؛ این جواب با ردِ وزن یال صفر تناقض ندارد. اعتبارِ کل گراف، حتی در این حالت، پیش از جست‌وجو بررسی می‌شود.

پرسش سوم: چرا برای A به Z عدد بسیار بزرگ برنمی‌گردانیم؟ پاسخ: Z تعریف شده، اما دسترسی ندارد؛ None نبودِ مسیر را صریح نشان می‌دهد. عدد قراردادیِ بزرگ ممکن است با هزینهٔ معتبر اشتباه شود. نامی که اصلاً تعریف نشده باشد، باید جداگانه خطا بدهد.

پرسش چهارم: آیا هزینهٔ پنج، تأخیر واقعیِ پنج میلی‌ثانیه را تضمین می‌کند؟ پاسخ: خیر؛ فقط جمع وزن‌های فرضی است. آزمایش، شبکه، حسگر، یادگیری ماشین یا مسیریابی عملیاتی اجرا نکرده است. منابع در ۲۵ مهر ۱۴۰۵ خوانده شده‌اند؛ این مطلب آموزش پایهٔ بازبینیِ قرارداد است و خبر پژوهشی تازه یا تضمین عملکرد محصول نیست.

منابع و مطالعهٔ بیشتر

• Poole و Mackworth؛ جست‌وجوی کم‌هزینه در کتاب نویسندگان، بخش 3.5.4
• Sedgewick و Wayne؛ کوتاه‌ترین مسیر جهتدار و Dijkstra، بخش 4.4
• Python heapq؛ کمینه، tuple و ورودی با اولویت تغییرکرده
• Python؛ مقایسهٔ واژه‌نامه‌ای tuple در دنباله‌ها

بررسی منابع: ۲۵ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.