无向无权图见另一篇文章《python无向无权图结构》，这篇讲无向带权图，并且给出一个地铁线路例子。

# -*- coding: UTF-8 -*-
#!/usr/bin/python

#-----------------------------------------------------------------------
# python3.6
# wgraph.py  
# 图的数据结构，以邻接表的方式存储结点
#-----------------------------------------------------------------------

import sys
import stdio
from instream import InStream
from outstream import OutStream

MAXL=99999

#-----------------------------------------------------------------------
#无向带权图
class WGraph:

    #构造函数，从文件或命令行读取边
    def __init__(self, filename=None, delimiter=None):
        self._e = 0
        self._adj = dict()
        self.lpath = []
        if filename is not None:
            instream = InStream(filename)
            while instream.hasNextLine():
                line = instream.readLine()
                names = line.split(delimiter)
                if(len(names)>0):   #防止无效的行
                    if(names[-1].isdigit()):
                        for i in range(1, len(names)-1):#最后一个元素表示边的权值
                            self.addEdge(names[0], names[i], names[-1])
                    else:
                        for i in range(1, len(names)):#最后一个元素不是数值表示无权图，默认权为1
                            self.addEdge(names[0], names[i], 1)
    
    # 
    def addEdge(self, v, w, weight):
        if not self.hasVertex(v): self._adj[v] = {}
        if not self.hasVertex(w): self._adj[w] = {}
        if not self.hasEdge(v, w):
            self._e += 1
            self._adj[v][w]=int(weight)
            self._adj[w][v]=int(weight)
            
    # 
    def adjacentTo(self, v):
        return iter(self._adj[v])
    
    #
    def vertices(self):
        return iter(self._adj)

    # 
    def hasVertex(self, v):
        return v in self._adj

    # 
    def hasEdge(self, v, w):
        return w in self._adj[v]
    
    # 
    def countV(self):
        return len(self._adj)
    
    # 
    def countE(self):
        return self._e
    
    # 
    def degree(self, v):
        return len(self._adj[v])
    
    def print_path(self, l, o):
        for x in l:
            #print("%s -> "%x, end='')
            o.write("%s -> "%x)
        #print("\n", end='')
        o.writeln()
    
    def allpath(self, s, t, o):
        self.lpath += [s]
        if(s==t):
            self.print_path(self.lpath, o)
        else:
            for v in self.adjacentTo(str(s)):
                if(v not in self.lpath):             
                    self.allpath(v, t, o)
        self.lpath.pop()
        
    def __findShorestNode(self, cost, visited):
        minDist=MAXL
        node=None
        for i in self.vertices():
            if (cost[i]<minDist) and (i not in visited):
                minDist=cost[i]
                node=i
        return node
    
    #返回从源结点s到所有每个结点的最短路径代价字典cost，和路径指向字典parents
    #cost[i]就是从s到达i的最小代价值，parents[i]存储从s到达i的最短路径上, i的前一个结点
    def dijkstra(self, s):
        cost={}
        visited=[s]
        parents={s:None}
        #初始化cost字典
        for v in self.vertices():
            if self.hasEdge(s, v):
                cost[v]=self._adj[s][v]
            else:
                cost[v]=MAXL
        cost[s]=0
        #初始化parents字典
        for i in self.adjacentTo(s):
            parents[i]=s
        
        node=self.__findShorestNode(cost, visited)
        while node:
            for i in self.adjacentTo(node): #所有node结点的邻居结点
                newcost = cost[node] + self._adj[node][i]
                if newcost<cost[i]:
                    parents[i]=node #最短路径到达i的路径上，i的上一个结点是node
                    cost[i]=newcost
            visited.append(node)
            node=self.__findShorestNode(cost, visited)

        return cost, parents
        
    # 
    def __str__(self):
        s = ''
        for v in self.vertices():
            s += v + '  '
            for w in self.adjacentTo(v):
                s += w + ' '
            s += '\n'
        return s

#-----------------------------------------------------------------------
#返回从图graph中源结点source到目的结点destination的最短路径
#返回空字典cost和列表spath，表示graph不是一个连通图
def shortestPath(graph, source, destination):
        s=source
        t=destination
        cost={}
        spath=[]
        if graph.hasVertex(s) and graph.hasVertex(t):
            cost, parents=graph.dijkstra(s)
            if MAXL in cost.values():   #graph不是一个连通图(只有一个连通分量)
                return {}, []
            path=[]
            p=parents[t]
            while(p):
                path.append(p)
                p=parents[p]
            spath = list(reversed(path))+[t]    
        return cost, spath  
# 
def main():
    #file = sys.argv[1]
    file1 = 'E:\\python_code\\GFmetro.txt'   #必须是utf-8编码
    outfile = 'E:\\python_code\\output.txt'
    graph = WGraph(file1)
    #stdio.writeln(graph)
    
    outsream = OutStream(outfile) 
    
    start=u"沥滘"
    end=u"广州东站"
    (cost, path) = shortestPath(graph, start, end)
    #print("path from %s to %s: cost=%d"%(start, end, cost[end]))
    if len(cost)>0 and len(path)>0:
        stdio.writeln("path from %s to %s: cost=%d"%(start, end, cost[end]))
        stdio.writeln(path)
    else:   #非连通图，结束程序
        stdio.writeln("the graph is not a fully connected graph")
        return 
    
    #print("all path")
    outsream.writeln("all path from  %s to %s: "%(start, end))
    graph.allpath(start, end, outsream)
    stdio.writeln("output to %s .... ok" % outfile)


if __name__ == '__main__':
    main()

#-----------------------------------------------------------------------
# PS:
class InStream:
    """
    可以从网络或文件输入
    """
    def __init__(self, fileOrUrl=None):
   
        self._buffer = ''
        self._stream = None
        self._readingWebPage = False

        if fileOrUrl is None:
            import stdio 
            self._stream = sys.stdin  # 从命令行输入
            return

        try:
            if sys.hexversion < 0x03000000:
                self._stream = open(fileOrUrl,'rU')
            else:
                self._stream = open(fileOrUrl, 'r', encoding='utf-8')
        except IOError:
            try:
                self._stream = urllib.urlopen(fileOrUrl)
                self._readingWebPage = True
            except IOError:
                raise IOError('No such file or URL: ' + fileOrUrl)
    def hasNextLine(self):
        """
        下一行非空，返回True
        """
        if self._buffer != '':
            return True
        else:
            self._buffer = self._stream.readline()
            if sys.hexversion < 0x03000000 or self._readingWebPage:
                self._buffer = self._buffer.decode('utf-8')
            if self._buffer == '':
                return False
            return True
    def readLine(self):
        """
        返回读出的一行
        仅对自动分行（非正常换行）的行会报错
        """
        if not self.hasNextLine():
            raise EOFError()
        s = self._buffer
        self._buffer = ''
        return s.rstrip('\n')

    def __del__(self):
        if self._stream is not None:
            self._stream.close()

class OutStream:
    """
    输出到文件或命令行
    """
    def __init__(self, f=None):#f是文件名，默认是命令行
        if f is None:
            self._stream = sys.stdout
        else:
            if sys.hexversion < 0x03000000:
                self._stream = open(f, 'w')#可以添加错误处理
            else:
                self._stream = open(f, 'w', encoding='utf-8')
    def writeln(self, x=''):
        """
        往流中写入串x，末尾加上换行符
        """
        if sys.hexversion < 0x03000000:
            x = unicode(x)
            x = x.encode('utf-8')
        else:
            x = str(x)
        self._stream.write(x)
        self._stream.write('\n')
        self._stream.flush()

    def __del__(self):
        self._stream.close()

程序运行输出：

path from 沥滘 to 广州东站: cost=7
['沥滘', '大塘', '客村', '广州塔', '珠江新城', '体育西路', '体育中心', '广州东站']

output to E:\python_code\output.txt .... ok

 

注意不要以此cost值作为出行的时间依据，因为文件中每两个站点间的时间值有待商榷，cost=1表示1个单位的时间，可能是1分钟，也可能是2分30秒，而且没有考虑换乘的时间因数 :P   当然，没人会按output.txt文件中的线路出行，除非他想在地铁里环游广佛~~

GFmetro.txt为广佛地铁图数据文件，见文末。对应的图如下：

若求 从魁奇路 到 区庄的最短线路，输出如下：

path from 魁奇路 to 区庄: cost=28
['魁奇路', '季华园', '同济路', '祖庙', '普君北路', '朝安', '桂城', '南桂路', '礌岗', '千灯湖', '金融高新区', '龙溪', '菊树', '西朗', '坑口', '花地湾', '芳村', '黄沙', '长寿路', '陈家祠', '西门口', '公园前', '农讲所', '烈士陵园', '东山口', '区庄']

 

GFmetro.txt 广佛地铁图数据文件内容，边角的线路待补充:P

魁奇路 季华园 1
同济路 季华园 1
同济路 祖庙 1
祖庙 普君北路 1
朝安 普君北路 1
桂城 朝安 1
南桂路 桂城 1
礌岗 南桂路 1
礌岗 千灯湖 1
千灯湖 金融高新区 1
金融高新区 龙溪 2
龙溪 菊树 2
西朗 菊树 2
西朗 鹤洞 1
鹤洞 沙涌 1
沙园 沙涌 凤凰新村 宝岗大道 燕岗 1
燕岗 石溪 1
石溪 南洲 1
沥滘 南洲 3

宝岗大道 昌岗 1
昌岗 晓港 1
晓港 中大 1
中大 鹭江 1
客村 鹭江 广州塔 赤岗 大塘 1
赤岗 磨碟沙 1
磨碟沙 新港东 1
新港东 琶洲 1
琶洲 万胜围 1

东涌 低涌 1
低涌 海傍 1
海傍 石碁 1
石碁 新造 1
新造 大学城南 1
大学城南 大学城北 1
大学城北 官洲 1
万胜围 车陂南 官洲 1
车陂南 车陂 1
车陂 黄村 1

鱼珠 三溪 1
三溪 东圃 1
东圃 车陂南 1
车陂南 科韵路 1
科韵路 员村 1
潭村 员村 1
猎德 潭村 1
猎德 珠江新城 1
珠江新城 五羊邨 1
五羊邨 杨箕 1
杨箕 东山口 体育西路 动物园 1
动物园 区庄 1
区庄 淘金 东山口 黄花岗 1
淘金 小北 1
小北 广州火车站 1
广州火车站 西村 1
西村 西场 1
西场 中山八 1
中山八 坦尾 1
坦尾 窖口 1

西朗 坑口 1
坑口 花地湾 1
花地湾 芳村 1
芳村 黄沙 1
黄沙 长寿路 1
长寿路 陈家祠 1
陈家祠 西门口 1
西门口 公园前 1
公园前 农讲所 1
农讲所 烈士陵园 1
烈士陵园 东山口 1
体育西路 石牌桥 1
石牌桥 岗顶 1
岗顶 华师 1
华师 五山 1
五山 天河客运站 1
体育西路 体育中心 1
体育中心 广州东站 1

萝岗 香雪 1
苏元 萝岗 1
暹岗 苏元 1
金峰 暹岗 1
黄陂 金峰 1
高塘石 黄陂 1
柯木塱 高塘石 1
龙洞 柯木塱 1
植物园 龙洞 2
植物园 长湴 2
天河客运站 长湴 2
天河客运站 燕塘 2
燕塘 天平架 1
天平架 沙河顶 1
沙河顶 黄花岗 1
黄花岗 区庄 1
区庄 东山口 1
东山口 东湖 1
东湖 团一大广场 1
团一大广场 北京路 1
北京路 海珠广场 1
海珠广场 一德路 1
一德路 文化公园 1
文化公园 黄沙 1
黄沙 如意坊 2
如意坊 坦尾 1

机场北 机场南 1
机场南 高增 1
高增 人和 1
人和 龙归 1
嘉禾望岗 龙归 黄边 白云大道北 1 
黄边 江夏 1
江夏 萧岗 1
萧岗 白云文化广场 1
白云文化广场 白云公园 1
飞翔公园 白云公园 1
三元里 飞翔公园 1
三元里 广州火车站 1
广州火车站 越秀公园 1
越秀公园 纪念堂 1
纪念堂 公园前 1
公园前 海珠广场 1
海珠广场 市二宫 1
市二宫 江南西 1
江南西 昌岗 1
昌岗 江泰路 1
江泰路 东晓南 2
东晓南 南洲 2
南洲 洛溪 2
洛溪 南浦 2
南浦 会江 2
会江 石壁 1
石壁 广州南站 1
石壁 谢村 2
谢村 钟村 2
钟村 汉溪长隆 2
汉溪长隆 南村万博 2
南村万博 员岗 2
员岗 板桥 1
板桥 大学城南 1

番禺广场 市桥 1
市桥 汉溪长隆 1
汉溪长隆 大石 1
大石 厦滘 1
厦滘 沥滘 1
沥滘 大塘 1
大塘 客村 1
客村 广州塔 1
广州塔 珠江新城 1
珠江新城 体育西路 1
体育西路 林和西 1
林和西 广州东站 1
广州东站 燕塘 1
燕塘 梅花园 1
梅花园 京溪南方医院 1
京溪南方医院 同和 1
同和 永泰 1
永泰 白云大道北 1


嘉禾望岗 白云东平 2
白云东平 夏良 2