设顶点V到W的最短路径为P。若我们将G中每条边的权重都加1，则P一定仍然是V到W的最短路径

这个命题是错误的。将G中每条边的权重都加1后，原本最短路径P的边权和也会加1，因此P不一定是V到W的最短路径。

举个例子，考虑以下图：

A --1--> B --1--> C
^       ^       |
|       |       1
2       3       |
|       |       v
D --1--> E --1--> F

其中每条边的权重已经标出。显然，从A到F的最短路径是A->B->C->F，边权和为3。现在，将图中每条边的权重都加1，得到以下图：

A --2--> B --2--> C
^       ^       |
|       |       2
3       4       |
|       |       v
D --2--> E --2--> F

此时，A到F的最短路径变为A->D->E->F，边权和为6，不再是原来的A->B->C->F，因此命题不成立。

相关问题

顶点v的权重为其他顶点v’到v的最短路径长度的最大值,权重最小的点为图g的中

首先，我们需要理解题目中给出的术语和概念。

题目中的图G是由一系列顶点和边组成的数据结构，其中顶点表示对象，边表示对象之间的关联关系。顶点v是图G中的一个节点，其他顶点v'表示非v的节点。路径长度指的是从一个节点到另一个节点经过的边的数量。最短路径长度是指从一个节点到另一个节点的路径中边的数量最少的那条路径。

题目中定义顶点v的权重为其他顶点v'到v的最短路径长度的最大值。也就是说，对于其他顶点v'到v的最短路径，我们选择路径长度最短的那条路径，并取其路径长度。

现在我们需要找到图G中权重最小的点，并称之为图G的中。换句话说，我们要找到图中一个顶点，使得它作为其他顶点到它本身的最短路径长度的最大值最小。

为了解决这个问题，可以采用以下步骤：

1. 遍历图G中的所有顶点，并计算每个顶点v'到v的最短路径长度。可以使用Dijkstra算法或Floyd-Warshall算法等最短路径算法实现这一步骤。

2. 对于每个顶点v，选择其他顶点v'到v的最短路径长度的最大值，并求出它们的最小值。这个最小值即为图G中权重最小的点。

在实际操作中，可能需要使用一个变量来追踪权重最小的点以及其对应的路径长度。

综上所述，顶点v的权重为其他顶点v'到v的最短路径长度的最大值，权重最小的点为图G的中。需要通过计算其他顶点到v的最短路径长度，并选择全局最小值来找到图G的中。

使用 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: 无法到达