【徹底比較】「Gemini3.0」と「ChatGPT5.1」を対決させてみた！

from __future__ import annotations
from typing import Dict, Hashable, List, Tuple, Any
import heapq
import math


class DirectedWeightedGraph:
    """
    加重付き有向グラフを表すクラス。
    ノードはハッシュ可能なオブジェクト（int, str など）であればOK。
    内部表現は
        adjacency[u][v] = weight
    という dict of dict を使う。
    """

    def __init__(self) -> None:
        # 工夫1: 隣接リストを dict-of-dict で管理
        #   - adjacency[u] = {v1: w1, v2: w2, ...}
        #   - エッジ追加・削除が O(1) に近い形で扱いやすい
        self.adjacency: Dict[Hashable, Dict[Hashable, float]] = {}

    # ========== ノード操作メソッド ==========

    def add_node(self, node: Hashable) -> None:
        """ノードを追加する（既に存在する場合は何もしない）"""
        if node not in self.adjacency:
            self.adjacency[node] = {}

    def remove_node(self, node: Hashable) -> None:
        """
        ノードを削除する。
        ・そのノードから出るエッジ
        ・そのノードへ向かうエッジ
        の両方を削除する。
        """
        if node not in self.adjacency:
            return

        # 工夫2: 「そのノードへのエッジ」もまとめて削除
        for u in list(self.adjacency.keys()):
            if node in self.adjacency[u]:
                del self.adjacency[u][node]

        # ノード自体を削除
        del self.adjacency[node]

    # ========== エッジ操作メソッド ==========

    def add_edge(self, u: Hashable, v: Hashable, weight: float) -> None:
        """
        有向エッジ u -> v を追加する。
        weight は 0 以上を想定（ダイクストラ法前提）。
        """
        if weight < 0:
            raise ValueError("ダイクストラ法では負の重みは扱えません。")

        # 工夫3: ノードが存在しなければ自動的に追加
        self.add_node(u)
        self.add_node(v)

        self.adjacency[u][v] = float(weight)

    def remove_edge(self, u: Hashable, v: Hashable) -> None:
        """エッジ u -> v を削除する（存在しない場合は何もしない）"""
        if u in self.adjacency and v in self.adjacency[u]:
            del self.adjacency[u][v]

    # ========== ダイクストラ法 ==========

    def dijkstra(self, start: Hashable) -> Tuple[Dict[Hashable, float], Dict[Hashable, Any]]:
        """
        ダイクストラ法で start から各ノードへの最短距離を計算する。

        戻り値:
            dist: 各ノードまでの最短距離 (到達不能な場合は math.inf)
            prev: 最短経路における直前ノード（start の prev[start] は None）
        """
        if start not in self.adjacency:
            raise ValueError(f"始点ノード {start!r} はグラフ内に存在しません。")

        # 初期化
        dist: Dict[Hashable, float] = {node: math.inf for node in self.adjacency}
        prev: Dict[Hashable, Any] = {node: None for node in self.adjacency}
        dist[start] = 0.0

        # 優先度付きキュー (距離, ノード)
        # 工夫4: 「遅延更新（lazy）」戦略を採用
        pq: List[Tuple[float, Hashable]] = []
        heapq.heappush(pq, (0.0, start))

        while pq:
            cur_dist, u = heapq.heappop(pq)

            # すでにより短い距離が見つかっている場合はスキップ
            if cur_dist > dist[u]:
                continue

            # 隣接ノードを緩和
            for v, w in self.adjacency[u].items():
                new_dist = dist[u] + w
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    prev[v] = u
                    heapq.heappush(pq, (new_dist, v))

        return dist, prev

    def reconstruct_path(self, start: Hashable, goal: Hashable,
                         prev: Dict[Hashable, Any]) -> List[Hashable]:
        """
        dijkstra の結果得られた prev を用いて、start から goal までの経路を復元する。
        到達不能な場合は空リストを返す。
        """
        if prev.get(goal, None) is None and start != goal:
            # start 自身以外で、prev が None の場合は到達不能
            return []

        path: List[Hashable] = []
        cur = goal
        while cur is not None:
            path.append(cur)
            cur = prev[cur]

        path.reverse()
        if path and path[0] == start:
            return path
        else:
            return []

    def shortest_paths_from(self, start: Hashable) -> Tuple[Dict[Hashable, float], Dict[Hashable, List[Hashable]]]:
        """
        始点 start から全ノードへの
        ・最短距離
        ・具体的な経路（ノード列）
        をまとめて返すヘルパーメソッド。
        """
        dist, prev = self.dijkstra(start)

        # 工夫5: 各ノードへの「経路」も同時に辞書で返す
        paths: Dict[Hashable, List[Hashable]] = {}
        for node in self.adjacency:
            paths[node] = self.reconstruct_path(start, node, prev)

        return dist, paths

    # ========== デバッグ・表示用 ==========

    def __str__(self) -> str:
        """グラフ構造を簡易的に文字列化して表示する"""
        lines: List[str] = []
        for u, edges in self.adjacency.items():
            if edges:
                for v, w in edges.items():
                    lines.append(f"{u} -> {v} (weight={w})")
            else:
                # 出次数 0 のノードも見えるようにする
                lines.append(f"{u} -> (no outgoing edges)")
        return "\n".join(lines)


# ===== 実行サンプル =====
if __name__ == "__main__":
    # グラフを作成
    g = DirectedWeightedGraph()

    # ノードとエッジを追加
    g.add_edge("A", "B", 2.0)
    g.add_edge("A", "C", 5.0)
    g.add_edge("B", "C", 1.0)
    g.add_edge("B", "D", 4.0)
    g.add_edge("C", "D", 1.5)
    g.add_edge("D", "E", 3.0)
    g.add_edge("A", "E", 10.0)

    print("=== グラフ構造 ===")
    print(g)
    print()

    # ダイクストラ法で A からの最短距離と経路を求める
    start_node = "A"
    dist, paths = g.shortest_paths_from(start_node)

    print(f"=== 始点 {start_node!r} からの最短距離と経路 ===")
    for node in sorted(dist.keys()):
        d = dist[node]
        if math.isinf(d):
            print(f"ノード {node!r} には到達不能")
        else:
            path_str = " -> ".join(str(x) for x in paths[node])
            print(f"ノード {node!r} までの距離: {d:.2f}, 経路: {path_str}")

    # ノード・エッジ削除の例
    print("\n=== ノード 'C' を削除した後のグラフ ===")
    g.remove_node("C")
    print(g)

    print("\n=== エッジ 'A' -> 'E' を削除した後のグラフ ===")
    g.remove_edge("A", "E")
    print(g)