节约里程法python代码

节约里程法是一种基于贪心算法的解决最短路径问题的方法。其思想是从起点开始，每次选择一个距离最短的可达节点，直到到达终点为止。

下面是用Python实现节约里程法的代码：

import sys

# 创建图的类
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

    def add_edge(self, u, v, weight):
        self.graph[u][v] = weight
        self.graph[v][u] = weight

    # 找到距离数组中距离最小的点的索引
    def min_distance(self, distance, shortest_path_set):
        min_dist = sys.maxsize
        min_index = 0

        for v in range(self.V):
            if distance[v] < min_dist and shortest_path_set[v] == False:
                min_dist = distance[v]
                min_index = v

        return min_index

    # 打印最短路径
    def print_shortest_path(self, parent, destination):
        if parent[destination] == -1:
            print(destination, end=' ')
            return
        self.print_shortest_path(parent, parent[destination])
        print(destination, end=' ')

    # 实现节约里程法算法
    def saving_mileage(self, source, destination):
        distance = [sys.maxsize] * self.V
        shortest_path_set = [False] * self.V
        parent = [-1] * self.V

        distance[source] = 0

        for _ in range(self.V - 1):
            u = self.min_distance(distance, shortest_path_set)
            shortest_path_set[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 and shortest_path_set[v] == False and distance[v] > distance[u] + self.graph[u][v]:
                    distance[v] = distance[u] + self.graph[u][v]
                    parent[v] = u

        print("最短路径为：")
        self.print_shortest_path(parent, destination)
        print("\n最短距离为：", distance[destination])

# 主函数
if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1, 2)
    g.add_edge(0, 2, 5)
    g.add_edge(1, 2, 4)
    g.add_edge(1, 3, 2)
    g.add_edge(2, 3, 1)
    g.add_edge(3, 4, 4)
    g.add_edge(3, 5, 2)
    g.add_edge(4, 5, 3)

    source = 0
    destination = 5
    g.saving_mileage(source, destination)

以上代码实现了节约里程法，并打印出了起点到终点的最短路径和最短距离。这段代码首先定义了一个图的类，包含创建图、添加边、找到最小距离等方法。然后在主函数中创建了一个图对象，并给图添加边。最后定义了起点和终点，并调用节约里程法的方法进行计算并打印结果。