文档章节

Dijkstra算法的粗略学习

syaokun219
 syaokun219
发布于 2014/06/06 00:16
字数 445
阅读 184
收藏 6
# -*- 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


© 著作权归作者所有

共有 人打赏支持
上一篇: Hello World
下一篇: AVL树的学习
syaokun219
粉丝 1
博文 4
码字总数 3017
作品 0
海淀
私信 提问
基于图论数据关联方法的目标跟踪

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

韦德爱老詹
04/27
0
0
像名字一样容易忘记的Dijkstra

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

dugangabc
2016/02/06
0
0
Dijkstra算法|单源最短路径|贪心算法

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

掬一捧
2012/09/26
0
0
28个不得不看的经典编程算法

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

xjhznick
2014/11/06
0
0
理解Dijkstra算法

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

桥头堡2015
2016/08/19
219
0

没有更多内容

加载失败,请刷新页面

加载更多

特斯拉车主成功破解了自己Model 3汽车

据汽车博客Electrek消息,一位特斯拉车主成功破解了自己Model 3汽车,还在此基础上运行了Ubuntu。 这位叫trsohmers的网友表示,“功劳大多要归到Ingineerix的头上,他花了数月才找到初始的那...

linuxCool
20分钟前
1
0
Gitbook : random errors when using gitbook plugin on running "gitbook serve"

在执行gitbook serve时,会有不定的失败错误 参考问题 :#1309 解决方案: 更新gitbook版本,这个问题似乎是3版本的问题 , 官方也不打算在这个版本解决了。 更新 到最新版本后, 不再出现问...

ol_O_O_lo
34分钟前
1
0
提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字

提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字: 作者:王健茜;断断续续一个多月才读完了《中国文化的深层结构》,这并不是一本难懂的书,之所以读得慢,源于对书中观点的思...

原创小博客
37分钟前
1
0
高德地图-行政区域接口

1、获取全国各省信息 https://restapi.amap.com/v3/config/district?extensions=all&key=应用Key&s=rsv3&output=json 2、获取下级行政区域信息 https://restapi.amap.com/v3/config/distric......

voole
49分钟前
4
0
集群介绍 ..

12月19日任务 18.1 集群介绍 18.2 keepalived介绍 18.3/18.4/18.5 用keepalived配置高可用集群 一.集群介绍 根据功能划分为两大类:高可用和负载均衡 高可用集群通常为两台服务器,一台工作,...

hhpuppy
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部