数据结构怎么输出最短路径

最短路径问题是图论中的经典问题，常用的算法有Dijkstra算法和Bellman-Ford算法。其中，Dijkstra算法适用于图上没有负权边的情况。下面是两种输出最短路径的方法：

1. 用Dijkstra算法输出最短路径

Dijkstra算法是一种用于求加权图中单个源点到其他所有顶点的最短路径的贪心算法。具体步骤如下：

- 初始化：将源点s的路径长度dist[s]设为0，其他所有路径长度dist[v]设为无穷大。
- 重复执行以下步骤，直到所有顶点的最短路径都求出来：
- 在未确定最短路径的顶点中，选取距离源点s最近的顶点u，标记顶点u的最短路径为确定的。
- 对于顶点u的每个邻接点v，如果当前路径长度加上u到v边的权值小于起始点到v的路径长度，就更新起始点到v的路径长度dist[v]。
- 最后，dist数组中的值即为源点到其他所有顶点的最短路径长度。

下面是一个使用Dijkstra算法输出最短路径的Python代码实现：

import heapq

def dijkstra(graph, start):
    heap = [(0, start)]
    visited = set()
    dist = {start: 0}
    while heap:
        (cost, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, weight in graph[u].items():
            new_cost = dist[u] + weight
            if v not in dist or new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(heap, (new_cost, v))
    return dist

graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 4, 'D': 1},
    'C': {'A': 3, 'B': 4, 'D': 2},
    'D': {'B': 1, 'C': 2}
}

distances = dijkstra(graph, 'A')
print(distances) # 输出：{'A': 0, 'B': 2, 'C': 3, 'D': 3}

上述代码中，我们实现了一个dijkstra函数，用于计算从指定起点到其他点的最短路径。

2. 使用谷歌地图API输出最短路径

谷歌地图提供了API，可以用于绘制两个点之间的最短路径。具体步骤如下：

- 获取谷歌地图API密钥。
- 根据谷歌地图API文档中的要求，构造请求URL，其中包含初始位置和目标位置的经纬度坐标。
- 发送HTTP请求，并解析返回结果中的路径坐标点。
- 将路径坐标点绘制在谷歌地图上。

下面是一个使用谷歌地图API输出最短路径的Python代码实现：

import requests
import json

def get_directions(origin, destination, api_key):
    url = ('https://maps.googleapis.com/maps/api/directions/json?'
           'origin={0}&destination={1}&key={2}').format(origin, destination, api_key)
    response = requests.get(url)
    json_data = json.loads(response.text)
    polyline = json_data['routes']['overview_polyline']['points']
    return polyline

# 例子
api_key = 'your_api_key'
origin = 'Toronto'
destination = 'Montreal'
path = get_directions(origin, destination, api_key)

上述代码中，我们使用requests库向谷歌地图API请求路径信息，并使用json库解析API返回结果中的路径坐标点。