文档章节

Dijkstra算法的粗略学习

syaokun219
 syaokun219
发布于 2014/06/06 00:16
字数 445
阅读 182
收藏 6
点赞 0
评论 0
# -*- coding: utf-8 -*-
#########################################################################
# Author: Yao Kun
# Created Time: 5/6/2014 PM 3:51:35
# File Name: dijkstra.py
# Description: 
#########################################################################
print "dijkstra"
INFINITE = 10000
# 打印邻接矩阵
def print_adj(adj):
    # 用于按行输出的临时string变量
    print "adj matrix --> "
    for row in adj:
        str_row = ""
        for ele in row:
            str_row += str(ele) + "\t"
        print str_row, "\n"
# 找到指定下标集合的最小值
def find_min(lst, allow_lst):
    tmp_min = INFINITE
    index = -1
    for i in range(0, len(lst)):
        if lst[i] < tmp_min and allow_lst[i] != 0:
            tmp_min = lst[i]
            index = i
    return index
# ori代表初始源点
def dijkstra(S, D, adj, dist, ori, point_num):
    print "Core Alg"
    
    # 这样表示的更容易理解
    path = []
    # 初始化D集合和dist集合,dist集合记录到某点的最小距离
    for i in range(0, point_num):
        if i == ori:
            dist.append(0)
        else:
            dist.append(INFINITE)
        path.append([ori])
        D.append(-1)
    # print "dist :", dist
    # print "D :", D
    # 一直循环直到S集合满
    while len(S) < point_num:
        # u代表当前正准备处理的顶点,取得最小值,然后并把这个点从D集合中取出
        u = find_min(dist, D)
        D[u] = 0
        # 添加u点到S集中
        S.append(u)
        for v in range(0, point_num):
            if adj[u][v] != INFINITE and D[v] != 0:
                # Relax 步骤
                if(dist[v] > dist[u] + adj[u][v]):
                    dist[v] = dist[u] + adj[u][v]
                    # 记录路径,删除原来的路径,将到u的路径和点v假如到新的路径中
                    path[v] = []
                    for i in range(0, len(path[u])):
                        path[v].append(path[u][i])
                    
                    path[v].append(v)
                   
    return path
# 单源点集合
S = []
D = []
# 保存到各个顶点距离的最小长度
dist = []
# 邻接矩阵
adj = [
    [INFINITE,    10,           INFINITE,       30,             100],
    [INFINITE,    INFINITE,     50,             INFINITE,       INFINITE],
    [INFINITE,    INFINITE,     INFINITE,       INFINITE,       10],
    [INFINITE,    INFINITE,     20,             INFINITE,       60],
    [INFINITE,    INFINITE,     INFINITE,       INFINITE,       INFINITE]
]
print_adj(adj)
path = dijkstra(S, D, adj, dist, 1, 5)
print path


© 著作权归作者所有

共有 人打赏支持
syaokun219
粉丝 1
博文 4
码字总数 3017
作品 0
海淀
基于图论数据关联方法的目标跟踪

目标跟踪方法包括生成类方法和判别类方法。与生成类方法最大的区别是,判别类方法分类器采用机器学习,训练中用到了背景信息,这样分类器就能专注区分前景和背景,所以判别类方法普遍都比生成...

韦德爱老詹 ⋅ 04/27 ⋅ 0

像名字一样容易忘记的Dijkstra

Dijkstra算法是经典的求解一个顶点到其他顶点的最短距离的算法。每次学习的时候总是觉得思路简单明了,但每当要用到时,就忘记了实现的细节。归根结底还是应用的少。相信做地图导航的应该对其...

dugangabc ⋅ 2016/02/06 ⋅ 0

Dijkstra算法|单源最短路径|贪心算法

单愿最短路径描述:给定带权有向图G=(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到...

掬一捧 ⋅ 2012/09/26 ⋅ 0

28个不得不看的经典编程算法

转载自:28个不得不看的经典编程算法 第一名:Union-find 严格地说,并查集是一种数据结构,它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构,使得编程复杂度降低到了令人...

xjhznick ⋅ 2014/11/06 ⋅ 0

理解Dijkstra算法

学习过最短路径问题的人都不会不知道Dijkstra算法。这个算法适用于解决无负权图的单源最短路径问题。这篇小文来谈谈如何理解这一算法。 这里首先给出一个Python 3的代码实现(以下代码出自P...

桥头堡2015 ⋅ 2016/08/19 ⋅ 0

优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆 ⋅ 2011/12/03 ⋅ 0

荷兰资格最老的程序员告诉你,如何用短短20分钟影响整个20世纪

  保持对同一个问题的思考   在那一个瞬间找到了答案   一个既是贪心又是最优的最短路径算法   1   人们总是在做一件事情:   找最短路径      公元前32世纪,苏美尔人在粘土...

超级数学建模 ⋅ 01/23 ⋅ 0

你不知道的关于计算机大师 Dijkstra 的事情

Dijkstra 的全名叫 Edsger Wybe Dijkstra(艾兹赫尔·韦伯·戴克斯特拉)。大部分中国程序员如果能记住这个名字是因为学过计算最短路径的「Dijkstra 算法」,然而大部分人都难以记住正确的拼...

oschina ⋅ 2016/04/27 ⋅ 25

微软面试、经典算法、编程艺术、红黑树4大系列总结

无私分享,造福天下 以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列4大经典原创系列作品与一些重要文章的集锦。 一、微软面试100题系列 横空出世,席...

长平狐 ⋅ 2013/01/06 ⋅ 0

1.1.1最短路(Floyd、Dijstra、BellmanFord)

转载自hr_whisper大佬的博客 一、Dijkstra 比较详细的迪杰斯特拉算法讲解传送门 Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。 使用邻...

fire_to_cheat_ ⋅ 03/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

骰子游戏代码开源地址

因为阿里云现在服务器已经停用了,所以上面的配置已经失效。 服务端开源地址:https://gitee.com/goalya/chat4.git 客户端开源地址:https://gitee.com/goalya/client4.git 具体运行界面请参考...

算法之名 ⋅ 18分钟前 ⋅ 0

设计模式--装饰者模式

装饰者模式 定义 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比生成子类更为灵活。 通用类图 意图 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比...

gaob2001 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部