《Mysql必知必会》读书笔记 jar包名中自动添加git commit id PyCharm教学视频学习笔记 《SQL基础教程》简要总结 《设计师要懂心理学》读书笔记 MySQL与MariaDB学习笔记 WDT (Folly) 安装指南 -- CentOS 7 [solved]Page build failed(Jekyll) 数据包过滤及分析实例 tshark tcpdump Scala Tour 学习总结 “Docker容器和容器云”读书笔记(1) “Docker Practice”读书笔记 “图解基础设施设计模式”小结 “图解服务器端网络架构”小结 Python网络安全编程 数据包解析笔记 华为挑战赛(1) DDoS攻击防御与云服务 基于网络回溯分析技术的异常行为分析 “Linux程序设计”小结(进程间通信) C语言编程规范(华为软件精英挑战赛) 2017阿里在线编程题--单源最短路径问题 2017年阿里在线编程题-- 数串分组 Uinx/Linux上的帮助查询命令 你懂C,所以C++不在话下 一篇特别长的总结(C专家编程) 程序员面试金典--笔记(精华篇) C陷阱与缺陷--笔记 半小时搭建电子商务网站--opencart linux网络知识和工具(持续更新) 网卡参数查询及设置工具ethtool 高性能流量生成工具trafgen(DDoS模拟) Linux流量控制工具TC 流量控制工具TC详细说明 tcpdump过滤数据包,结果不对? Lecture 网络攻击与防御技术笔记 gotgit-git权威指南 高效使用MacOS所要知道的 shell内置字符串处理 配置ntp(知其所以然) 360黑客攻防技术分享会--记录 中毒U盘恢复--快捷键病毒 Tor--anonymity network介绍(PPT) IBM bluemix 再读《Linux Shell脚本攻略》 linux shell 学习摘记(9) linux shell 学习摘记(8) linux shell 学习摘记(7) linux shell 学习摘记(6) linux shell 学习摘记(5) linux shell 学习摘记(4) linux shell 学习摘记(3) linux shell 学习摘记(2) linux shell 学习摘记(1) firefox vim 插件 vimperator A Byte of Vim 笔记 windows注册表小知识 安全测试工具篇(开源&商业) 安全及性能测试工具(网站收集) 性能测试工具 屡试不爽的“3个”iPad使用技巧 Shell Shortcuts(和Tab键一样实用) vim--自动添加jekyll post信息头 vim 自动给文件添加头部信息 GitHub Tips (很实用,值得收藏) Linux路由、防火墙、NAT命令

2017阿里在线编程题--单源最短路径问题

2017年03月06日

原文链接: http://codeshold.me/2017/03/alialgorithm_dijkstra.html

题目

西湖是杭州最有名的风景区,每年到西湖旅游的客户非常多,大家各自从不同的地方出发到西湖,交通问题非常令人头疼。阿里小二J准备通过高德地图实时数据和只能推荐帮助大家解决这个问题。
现在有一组地理坐标,地理位置用5位以内的大写字母表示。高德地图会根据实时的车流情况预估实时路况:从地理位置1到地理位置2之间的用时,单位为分钟。地理位置之间和用时之间都用英文逗号分隔。比如:WSX,BQB,20,表示从WSX位置到BQB位置,需要20分钟。注意,仅凭这一条信息不能代表BQB到WSX也为20分钟。西湖的地理位置用XH表示
系统保障:
地理位置不重名
至少存在一条从目的地到西湖的路径
实时路况数量不超过10000
地理位置数不超过100
实时路况的分钟数为1到21亿之间的正整数
请计算从给出目的地理位置(非XH的任意地理位置)到西湖的最少用时路径

解答

一个典型的Dijkstra算法, 但自己算法确实生疏了(要抓紧时间开始刷题了),秉承着诚信的原则,半小时内确实没有实现!

有时间了提供一个基于优先队列的实现!

python实现

# -*- encoding:utf-8 -*-


class BuildGraph(object):
    def __init__(self, filename):
        self.file = filename
        self.matrix = [[float('inf') for _ in range(100)] for _ in range(100)]
        self.v2idict = {}
        self.i2vdict = {}
        self.start = 0
        self.end = 0
        self.__parse_file()

    def vcount(self):
        return len(self.v2idict)

    def __parse_file(self):
        with open(self.file, 'r') as f:
            count = int(f.readline().strip('\n\r '))
            for i in range(1, count+1):
                data = f.readline().strip('\n\r ').split(',')
                if data[0] not in self.v2idict:
                    index = len(self.v2idict)
                    self.v2idict[data[0]] = index
                    self.i2vdict[index] = data[0]
                if data[1] not in self.v2idict:
                    index = len(self.v2idict)
                    self.v2idict[data[1]] = index
                    self.i2vdict[index] = data[1]
                line = self.v2idict[data[0]]
                col = self.v2idict[data[1]]
                self.matrix[line][col] = int(data[2])
            self.start = self.v2idict[(f.readline().strip('\n\r '))]
            self.end = self.v2idict['XH']


class DijkstraAlgorithm(object):
    def __init__(self, graph):
        self.matrix = graph.matrix
        self.start = graph.start
        self.end = graph.end
        self.i2vdict = graph.i2vdict
        self.vcount = graph.vcount()
        self.path = []
        self.dist = [float('inf')] * self.vcount
        self.__remain_set = set()
        self.i2vdict = graph.i2vdict
        for i in range(0, self.vcount):
            self.dist[i] = self.matrix[self.start][i]
            self.__remain_set.add(i)
        self.__deal()

    def __get_min(self):
        min_vertex = -1
        min_index = -1
        for i in self.__remain_set:
            if min_vertex == -1:
                min_vertex = i
                min_index = i
            if self.dist[i] < min_vertex:
                min_vertex = self.dist[i]
                min_index = i
        return min_index

    def __deal(self):
        self.path.append(self.start)
        self.__remain_set.remove(self.start)
        for n in range(0, self.vcount-2):
            min = self.__get_min()
            self.__remain_set.remove(min)
            if min == self.end:
                break
            for i in self.__remain_set:
                if self.dist[i] > self.dist[min] + self.matrix[min][i]:
                    self.dist[i] = self.dist[min] + self.matrix[min][i]
                    if i == self.end:
                        self.path.append(min)

    def print_result(self):
        print "Path: ",
        for i in range(0, len(self.path)):
            print self.i2vdict[self.path[i]], "-->",
        print self.i2vdict[self.end]
        print "Cost: ", self.dist[self.end]


if __name__ == "__main__":
    test = BuildGraph("test.txt")
    deal = DijkstraAlgorithm(test)
    deal.print_result()

知识共享许可协议
SWF's Hacking Dreamonephone 创作,采用 知识共享 署名-非商业性使用 4.0 国际 许可协议进行许可。
© 2011-2018. All rights reserved by onephone. Powerd by Jekyll.