请编写代码将该图该图表示成有向图,并求该图形的两点之间最短路径及长度。如果不可达则写成-1。
时间: 2023-03-12 12:50:57 浏览: 85
我可以提供一个基于Python的示例代码,可以帮助您实现您的要求:
```python
# 建立有向图
graph = {
'A': {'B': 5, 'C': 2},
'B': {'A': 5, 'C': 1, 'D': 3},
'C': {'A': 2, 'B': 1, 'D': 4, 'E': 2},
'D': {'B': 3, 'C': 4, 'E': 3},
'E': {'C': 2, 'D': 3}
}# 定义一个函数,用于求两点之间的最短路径及长度
def dijkstra(graph, start, end):
# 将图中的所有节点初始化为无穷大
infinity = float('inf')
dist = {node: infinity for node in graph}
# 将起点距离设为0
dist[start] = 0
# 建立一个字典,用于记录路径
path = {}
# 定义一个优先队列,以起点为初始状态
queue = [start]
# 开始循环,当队列为空时,说明所有节点都已搜索完毕
while queue:
curr_node = queue.pop(0)
curr_dist = dist[curr_node]
# 如果当前节点为目标节点,则结束搜索
if curr_node == end:
break
# 否则,将当前节点的邻节点进行搜索
for next_node in graph[curr_node]:
next_dist = curr_dist + graph[curr_node][next_node]
# 如果当前节点的邻节点距离小于之前记录的距离,则更新距离
if dist[next_node] > next_dist:
dist[next_node] = next_dist
path[next_node] = curr_node
queue.append(next_node)
# 如果目标节点不可达,则返回-1
if dist[end] == infinity:
return -1
# 如果目标节点可达,则求出最短路径及长度
curr_node = end
shortest_path = [curr_node]
while curr_node != start:
curr_node = path[curr_node]
shortest_path.append(curr_node)
shortest_path.reverse()
shortest_dist = dist[end]
return shortest_path, shortest_dist# 调用函数求两点之间的最短路径及长度
shortest_path, shortest_dist = dijkstra(graph, 'A', 'E')
print('最短路径:', shortest_path)
print('最短路径长度:', shortest_dist)
```