例4[最小代价通讯网络]城市之间所有可能的通信连接 可被视作一个无向图，图的每条边都被赋予一个权值，权值 表示建成由这条边所表示的通信连接所要付出的代价。包含 图中所有顶点（城市)的连通子图都是一个可行解。设所有 权值都为负，则所有可能的可行解都可表示成无向图的一组 生成树，而最优解就是其中具有最小代价的生成树。 在这个问题中，需要选择一个无向图中的边集合的子集， 这个子集必须满足如下限制条件：所有的边构成一个生成树。 而优化函数是子集中所有边的权值之和。 例5[最短路径问题]在有向图中求一个顶点到另一个顶 点的最短路径。（如路由问题）例4 [最小代价通讯网络] 城市之间所有可能的通信连接 可被视作一个无向图，图的每条边都被赋予一个权值，权值 表示建成由这条边所表示的通信连接所要付出的代价。包含 图中所有顶点（城市）的连通子图都是一个可行解。设所有 权值都为负，则所有可能的可行解都可表示成无向图的一组 生成树，而最优解就是其中具有最小代价的生成树。 在这个问题中，需要选择一个无向图中的边集合的子集， 这个子集必须满足如下限制条件：所有的边构成一个生成树。 而优化函数是子集中所有边的权值之和。 例5 [最短路径问题] 在有向图中求一个顶点到另一个顶 点的最短路径。（如路由问题）