贪心算法最短路径问题:编程实现

以下是使用贪心算法求解单源最短路径问题的Python代码实现：

def dijkstra(graph, start):
    # 初始化距离字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # 初始化已访问节点集合
    visited = set()
    # 循环遍历所有节点
    while len(visited) != len(graph):
        # 找到未访问节点中距离最小的节点
        node = min(set(dist.keys()) - visited, key=dist.get)
        # 标记该节点为已访问
        visited.add(node)
        # 更新与该节点相邻节点的距离
        for neighbor, distance in graph[node].items():
            new_distance = dist[node] + distance
            if new_distance < dist[neighbor]:
                dist[neighbor] = new_distance
    return dist

其中，`graph`是一个字典，表示图的邻接表；`start`是起点节点。该函数返回一个字典，表示从起点到各个节点的最短距离。

以下是使用贪心算法求解多机调度问题的Python代码实现：

def schedule(tasks, m):
    # 初始化每台机器的任务时间
    machines = [0] * m
    # 循环遍历所有任务
    for task in tasks:
        # 找到当前空闲时间最短的机器
        min_machine = min(machines)
        # 将任务分配给该机器
        machines[machines.index(min_machine)] += task
    return max(machines)

其中，`tasks`是一个列表，表示所有任务的时间；`m`是机器数量。该函数返回一个整数，表示完成所有任务的最短时间。