邻接表创建无向图算最短路径

要求算出无向图中两个节点之间的最短路径，可以使用Dijkstra算法。而邻接表是一种常见的图的表示方法，可以方便地用来实现Dijkstra算法。

具体步骤如下：

1. 创建一个空的邻接表，其中每个节点对应一个链表。

2. 遍历所有的边，对于每条边 (u,v)，在邻接表中为节点u和节点v分别添加一个指向对方的边。

3. 初始化起点的距离为0，将起点加入一个优先队列中。

4. 重复执行以下步骤，直到优先队列为空或者目标节点已经被访问到：

a. 从优先队列中弹出一个距离起点最近的节点u，将其标记为已访问。

b. 遍历节点u的所有邻居v，如果v没有被访问过，则更新v的距离为min(dist[v], dist[u]+w(u,v))，其中dist[v]表示从起点到节点v的距离，w(u,v)表示边(u,v)的权重。

c. 如果v的距离被更新了，则将v加入优先队列中。

5. 最终得到的dist数组中，dist[i]表示从起点到节点i的最短距离。

下面是一个示例代码，假设输入的图是一个无向图，用邻接表表示，起点为0，目标节点为5：

import heapq

def dijkstra(graph, start, end):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    visited = [False] * n
    queue = [(0, start)]
    while queue:
        d, u = heapq.heappop(queue)
        if visited[u]:
            continue
        visited[u] = True
        if u == end:
            return dist[end]
        for v, w in graph[u]:
            if not visited[v] and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(queue, (dist[v], v))
    return float('inf')

# 例子中的图
graph = [
    [(1, 2), (2, 3)],
    [(0, 2), (2, 4), (3, 3)],
    [(0, 3), (1, 4), (3, 1)],
    [(1, 3), (2, 1), (4, 5)],
    [(3, 5), (5, 2)],
    [(4, 2)]
]
start = 0
end = 5
distance = dijkstra(graph, start, end)
print(distance) # 9

在这个例子中，图有6个节点，边的权重用元组表示，如(1, 2)表示从节点1到节点2的边的权重为2。通过调用dijkstra函数，可以计算出从节点0到节点5的最短路径长度为9。