浅议GPS算法

# -*- coding:utf-8 -*-
from collections import deque

# 创建视图内容
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

search_queue = deque()

search_queue += graph["you"]


def person_is_lawyer(name):
    """
    模拟一位律师,假设名字最后一位是m的人,就是律师

    :param name:传入的每一个名字
    :return:
    """
    return name[-1] == 'm'


def fn_search(search_queue):
    """
    寻找律师主函数, 为了防止视图死循环,加入了判断.

    :param search_queue:创建一个双端队列(此处为左出右进)
    :param person 从队列中取出的每一个人名
    :return:
    """

    searched = []  # 这个数组用于记录检查过的人

    while search_queue:  # 只要队列不为空，
        person = search_queue.popleft()  # 就取出其中第一个人

        if person not in searched:  # 仅当这个人没检查过时才检查
            if person_is_lawyer(person):  # 检查这个人是否是律师
                print(person + " is a lawyer!")  # 是律师
                return True

            else:
                search_queue += graph[person]  # 不是律师。将这个人的朋友都加入到搜索队列
                searched.append(person)  # 将这个人标记为检查过

    return False  # 如果到达了这里，就说明队列中没有人是律师。


fn_search(search_queue)

# -*- coding:utf-8 -*-

# 创建graph视图表
graph = dict()
graph["you"] = ["alice", "bob", "claire"]
graph["start"] = dict()
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = dict()
graph["a"]["fin"] = 1
graph["b"] = dict()
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = dict()

# 创建节点开销表
infinity = float("inf")
costs = dict()
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# 创建父节点散列表
parents = dict()
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

# 创建一个数组,用来记录已经处理过的节点.
processed = list()


def find_lowest_cost_node(_costs):
    """
    找出开销最低的节点
    :param _costs:
    :return:
    """

    lowest_cost = float("inf")  # 定义默认开销无穷大
    lowest_cost_node = None

    for node in _costs:  # 遍历所有的节点
        cost = _costs[node]

        if cost < lowest_cost and node not in processed:  # 如果当前节点的开销更低且未处理过,
            lowest_cost = cost  # 就将其视为开销最低的节点.
            lowest_cost_node = node

    return lowest_cost_node


def dijkstra():
    """
    迪克斯特拉算法
    :param node: 获取的一个节点
    :return:
    """

    node = find_lowest_cost_node(costs)  # 在未处理的节点中找出开销最小的节点

    while node is not None:  # 这个while循环在所有节点都被处理过后结束
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():  # 遍历当前节点的所有邻居
            new_cost = cost + neighbors[n]

            if costs[n] > new_cost:  # 如果经当前节点前往该邻居更近
                costs[n] = new_cost  # 就更新邻居的开销
                parents[n] = node  # 同时将该邻居的父节点设置为当前节点
        processed.append(node)  # 将当前节点标记为处理过
        node = find_lowest_cost_node(costs)  # 找出接下来要处理的节点,并循环


dijkstra()