python实现：十字链表存储图，寻找最短路径

在Python中，我们可以使用十字链表（Cross-Linked List）来存储稀疏图，特别是无向图。十字链表是一种数据结构，它将图的邻接节点连接到当前节点的左右两个位置，这样可以高效地访问相邻节点。对于寻找最短路径，我们通常会使用迪杰斯特拉算法（Dijkstra's Algorithm）或贝尔曼-福特算法（Bellman-Ford Algorithm）。

以下是使用十字链表和迪杰斯特拉算法来寻找最短路径的一个简单例子：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.dist = float('inf')
        self.prev = None

class CrossLinkedListGraph:
    def __init__(self, edges):
        self.root = Node(0)
        self.nodes = {0: self.root}
        for src, dest, weight in edges:
            node_src = self.nodes.get(src, Node(src))
            node_dest = self.nodes.get(dest, Node(dest))
            node_src.left = node_dest
            node_src.right = node_dest
            node_dest.dist = min(node_dest.dist, weight)
            node_dest.prev = node_src

    def dijkstra(self, start_node):
        visited = set()
        queue = [(start_node.dist, start_node)]
        while queue:
            curr_dist, curr_node = queue.pop(0)
            if curr_node not in visited:
                visited.add(curr_node)
                for neighbor in (curr_node.left, curr_node.right):
                    new_dist = curr_dist + neighbor.dist
                    if neighbor.dist > new_dist:
                        neighbor.dist = new_dist
                        neighbor.prev = curr_node
                        queue.append((new_dist, neighbor))
        return self.root.dist

# 示例
edges = [(1, 2, 5), (2, 3, 1), (1, 4, 2), (4, 3, -3)]
g = CrossLinkedListGraph(edges)
shortest_path = g.dijkstra(g.root)

在这个例子中，`dijkstra`函数会返回从根节点到其他所有节点的最短路径长度。`prev`属性用于回溯最近的前驱节点，构建路径。