轮子：Julia做Graph

nesteiner · 2020 年3 月 5 日 06:43

这是去年做的轮子，现在学函数式编程挺久了，有空想重新构造下代码。
顺便说一下，当初学元编程不怎么会，宏写得不怎么好

# graph.jl
include("List.jl")

import .LinkedList:Queue
import .LinkedList:push
import .LinkedList:remove
import .LinkedList:@lengthof
#--------------------------------#
#            vertex              #
#--------------------------------#

@enum Color White=0 Grey=1 Black=2

mutable struct Vertex{T}
    value::T
    color::Color
    index::UInt64
    hop::Int
end

Vertex{T}(value::T) where T = Vertex{T}(value,White,0,0)

#----------------#
#       ==       #
#----------------#
Base.:(==)(vertex1::Vertex{T},vertex2::Vertex{T}) where T = vertex1.value == vertex2.value

#----------------#
#     valueof    #
#----------------#
valueof(vertex::Vertex{T}) where T = vertex.value

#----------------#
#     indexof    #
#----------------#
indexof(vertex::Vertex{T}) where T = vertex.index
setindex(vertex::Vertex{T},index::UInt64) where T = vertex.index=index
isvisted(vertex::Vertex{T}) where T = !(notvisited(vertex))
visited!(vertex::Vertex{T}) where T = vertex.color=Black
notvisited(vertex::Vertex{T}) where T = vertex.color == White
# export Vertex
# export Color
# export White
# export Black
# export Grey
# export ==
# export valueof
# export indexof
# export setindex
# end

#--------------------------------#
#            adjlist             #
#--------------------------------#
#module adjlist
#import ..vertex:Vertex

mutable struct AdjList{T}
    vertex::Vertex{T}
    edge::Set{Tuple{Vertex{T},Int}} #contain vertex and weight
end

AdjList{T}(value::T) where T = AdjList{T}(Vertex{T}(value),Set{Tuple{Vertex{T},Int}}())

#Base.iterate(adjlist::AdjList{T}) where T = (adjlist.vertex,adjlist.edge)
#----------------#
#   vertex-of    #
#----------------#
vertexof(adjlist::AdjList{T}) where T = adjlist.vertex

#----------------#
#    edge-of     #
#----------------#

# export AdjList
# export vertexof
#export iterate
#end

#--------------------------------#
#             graph              #
#--------------------------------#
#module graph

# import ..vertex:Vertex
# import ..vertex:indexof
# import ..adjlist:vertexof
# import ..adjlist:AdjList

mutable struct Graph{T}
    vcount::Int
    ecount::Int
    list::Set{AdjList{T}}
    hasdirection::Bool
end

Graph{T}(direct=true) where T = Graph{T}(0,0,Set{AdjList{T}}(),direct)
#----------------#
#    vertexof    #
#----------------#
vertexof(graph::Graph{T},index::UInt64) where T =
    begin
        for current in graph.list
            if indexof(current.vertex) == index
                return current.vertex
            end
        end
    end
#----------------#
#   getadjlist   #
#----------------#
getadjlist(graph::Graph{T},index::UInt64) where T = begin
    for current in graph.list #AdjList
        if indexof(vertexof(current)) == index
            return current
        end
    end
end


# export Graph
# export getadjlist

# end



#--------------------------------#
#           function             #
#--------------------------------#
# using .vertex
# using .adjlist
# using .graph


#----------------#
#     edgeof     #
#----------------#
edgeof(graph::Graph{T},index::UInt64) where T = begin
    adjlist=getadjlist(graph,index)
    if adjlist != nothing
        adjlist.edge
    end
end

edgeof(adjlist::AdjList{T}) where T = adjlist.edge
#--------------------------------#
#            append              #
#--------------------------------#

#------------------------#
#   add vertex -> index  #
#------------------------#
function append_vertex!(graph::Graph{T},value::T) where T# return index
    for adjlist in graph.list #AdjList
        if value == valueof(vertexof(adjlist))
            return
        end
    end

    new_elmt = AdjList{T}(value)
    index=hash(value)
    graph.vcount+=1
    setindex(vertexof(new_elmt),index)
    push!(graph.list,new_elmt)
    index

end

#------------------------#
#add egde with two index #
#------------------------#
function append_edge!(graph::Graph{T},index1::UInt64,index2::UInt64,w::Int=0) where T# w: 权重
    #judge that if index1 and index2 is in each vertex of graph.list(AdjList)
    adjlist1=getadjlist(graph,index1)
    adjlist2=getadjlist(graph,index2)
    if adjlist1 == nothing || adjlist2 == nothing
        return
    end

    if graph.hasdirection == true
        push!(edgeof(adjlist1),(vertexof(adjlist2),w))
    else
        push!(edgeof(adjlist1),(vertexof(adjlist2),w))
        push!(edgeof(adjlist2),(vertexof(adjlist1),w))
    end
    
    graph.ecount+=1
end

这是List.jl

module LinkedList

abstract type SingleList{T} end
#----------------#
#    ListElmt    #
#----------------#
mutable struct ListElmt{T}
    value::T
    next::Union{Nothing,ListElmt{T}}
end

ListElmt{T}(data::T) where T = ListElmt{T}(data,nothing)

#----------------#
#    DListElmt   #
#----------------#
mutable struct DListElmt{T}
    value::T
    prev::Union{Nothing,DListElmt{T}}
    next::Union{Nothing,DListElmt{T}}
end

DListElmt{T}(data::T) where T = DListElmt{T}(data,nothing,nothing)


#----------------#
#     mode       #
#----------------#
struct Mode
    push_fn::Int
    pop_fn::Int
end

const Push_Front=0
const Push_Back=1
const Pop_Front=2
const Pop_Back=3
#-------------------#
#      List         #
#-------------------#
mutable struct List{T} <: SingleList{T}
    size::Int
    head::Union{Nothing,ListElmt{T}}
    tail::Union{Nothing,ListElmt{T}}
    mode::Mode
end

List{T}() where T = List{T}(0,nothing,nothing,Mode(Push_Back,Pop_Back))


#------------------#
#     DList        #
#------------------#
mutable struct DList{T}
    size::Int
    head::Union{Nothing,DListElmt{T}}
    tail::Union{Nothing,DListElmt{T}}
    mode::Mode
end

DList{T}() where T = DList{T}(0,nothing,nothing,Mode(Push_Back,Pop_Back))

#------------------#
#      Queue       #
#------------------#
mutable struct Queue{T} <: SingleList{T}
    size::Int
    head::Union{Nothing,ListElmt{T}}
    tail::Union{Nothing,ListElmt{T}}
    mode::Mode
end

Queue{T}() where T = Queue{T}(0,nothing,nothing,Mode(Push_Back,Pop_Front))

#------------------#
#     Stack        #
#------------------#
mutable struct Stack{T} <: SingleList{T}
    size::Int
    head::Union{Nothing,ListElmt{T}}
    tail::Union{Nothing,ListElmt{T}}
    mode::Mode
end

Stack{T}() where T = Stack{T}(0,nothing,nothing,Mode(Push_Front,Pop_Front))

#----------------#
#      macro     #
#----------------#

# Q? is need for esc ??
macro lengthof(list)
    quote
        $list.size
    end |> esc
end

macro valueof(elmt)
    quote
        $elmt.value
    end |> esc
end

macro nextof(elmt)
    quote
        $elmt.next
    end |> esc
end



#-----------------#
#    push fn      #
#-----------------#
function push_back(list::SingleList{T},data::T) where T
    new_elmt=ListElmt{T}(data)
    
    if 0 == @lengthof list
        list.head=list.tail=new_elmt
    else
        list.tail=list.tail.next=new_elmt
    end
    list.size+=1
end

function push_back(list::DList{T},data::T) where T
    new_elmt=DListElmt{T}(data)

    if 0 == @lengthof list
        list.head=list.tail=new_elmt
    else
        new_elmt.prev=list.tail
        list.tail.next=new_elmt
        list.tail=new_elmt
    end
    list.size+=1
end

function push_front(list::SingleList{T},data::T) where T
    new_elmt=ListElmt{T}(data)

    if 0 == @lengthof list
        list.head=list.tail=new_elmt
    else
        new_elmt.next=list.head
        list.head=new_elmt
    end
    list.size+=1
end

function push_front(list::DList{T},data::T) where T
    new_elmt=DListElmt{T}(data)

    if 0 == @lengthof list
        list.head=list.tail=new_elmt
    else
        new_elmt.next=list.head
        list.head.prev=new_elmt
        list.head=new_elmt
    end

    list.size+=1
end

#--------------#
#    pop fn    #
#--------------#
function pop_back(list::SingleList{T}) where T
    if list.size==0
        return nothing
    end

    if list.size==1
        res=list.head.value
        list.head=list.tail=nothing
        list.size-=1
        return res
    end
    
    current=list.head    
    for i in 1:list.size-2
        current=current.next
    end

    res=list.tail.value
    list.tail=current
    list.size-=1
    res
end

function pop_back(list::DList{T}) where T
    if list.size==0
        return nothing
    end

    if list.size==1
        res=list.head.value
        list.head=list.tail=nothing
        list.size-=1
        return res
    end
    
    res=list.tail.value
    list.tail=list.tail.prev
    list.tail.next=nothing

    list.size-=1
    return res
end

function pop_front(list::SingleList{T}) where T
    if list.size==0
        return nothing
    else

        res=list.head.value
        list.head=list.head.next
        list.size-=1
        return res
    end
end

function pop_front(list::DList{T}) where T
    if list.size==0
        return nothing
    else

        res=list.head.value
        list.head=list.head.next
        list.head.prev=nothing
        list.size-=1
        return res
    end

end

#---------------#
#  interface    #
#---------------#
function push(list::SingleList{T},data::T) where T
    if list.mode.push_fn == Push_Front
        push_front(list,data)
    else
        push_back(list,data)
    end
end

function push(list::DList{T},data::T) where T
    if list.mode.push_fn == Push_Front
        push_front(list,data)
    else
        push_back(list,data)
    end
end

function remove(list::SingleList{T}) where T
    if list.mode.pop_fn == Pop_Back
        return pop_back(list)
    else
        return pop_front(list)
    end
end

function remove(list::DList{T}) where T
    if list.mode.pop_fn == Pop_Back
        return pop_back(list)
    else
        return pop_front(list)
    end
end


#-----------------#
#    iterate      #
#-----------------#
Base.iterate(list::Union{SingleList{T},DList{T}}) where T = list.size==0 ? nothing : ( list.head, list.head)
Base.iterate(list::Union{SingleList{T},DList{T}},state::Union{ListElmt{T},DListElmt{T}}) where T = state.next==nothing ? nothing : ( state.next, state.next)

#--------------#
#   appendix   #
#--------------#

#--------------#
#    contain   #
#--------------#
function contain(list::Union{SingleList{T},DList{T}},data::T) where T
    for current in list
        if @valueof(current) == data
            return true
        end
    end
    
    return false
end

#--------------#
#    print     #
#--------------#

function Base.print(list::Union{SingleList{T},DList{T}}) where T
    for current in list
        print(@valueof(current),'\t')
    end
    println()
end


# export List
# export DList
# export Queue
# export Stack
# export contain
# export push
# export remove
# export print

end

dijkstra算法

# dijkstra.jl
 include("graph.jl")
include("load_weight.jl")
#--------------------------------#
#            Dijkstra            #
#--------------------------------#
function dijkstra(graph::Graph{T},start::UInt64,last::UInt64) where T
    weight=load_weight(graph)
    for (k,v) in weight
        println(k,'\t',v)
    end
    #need a list for save
    list=Dict{UInt64,Int}()
    #init list
    for adjlist in graph.list
        vertex=vertexof(adjlist)
        list[indexof(vertex)] = abs(typemax(Int))
    end
    
    for (vertex,) in edgeof(graph,start)
        list[indexof(vertex)] = weight[start][indexof(vertex)]
        vertex.color = Grey
        vertexof(graph,start).color = Black
    end

    for (minindex,) in list
        if vertexof(graph,minindex).color == Grey
            for (vertex,) in edgeof(graph,minindex)
                if vertex.color != Black
                    list[indexof(vertex)]=min(list[indexof(vertex)],list[minindex]+weight[minindex][indexof(vertex)])
                    vertex.color = Grey
                end
            end
            vertexof(graph,minindex).color = Black
        end
    end

    return list[last]
end

index=Vector{UInt64}(undef,7)

graph=Graph{Int}()
for i in 1:7
    index[i]=append_vertex!(graph,i)
end

append_edge!(graph,index[1],index[2],2)
append_edge!(graph,index[1],index[3],5)
append_edge!(graph,index[2],index[4],1)
append_edge!(graph,index[2],index[5],3)
append_edge!(graph,index[3],index[2],6)
append_edge!(graph,index[3],index[6],8)
append_edge!(graph,index[4],index[5],4)
append_edge!(graph,index[5],index[7],9)
append_edge!(graph,index[6],index[7],7)

res=dijkstra(graph,index[1],index[7])
print(res)

# load_weight.jl
#include("graph2.jl")

function load_weight(graph::Graph{T}) where T
    dict=Dict{UInt64,Dict{UInt64,Int}}()
    
    for adjlist in graph.list#Set of AdjList |vertex,Set{Tuple}|
        vertex1,edge=vertexof(adjlist),edgeof(adjlist)
        dict[indexof(vertex1)]=Dict{UInt64,Int}()
        for (vertex2,weight) in edge
            dict[indexof(vertex1)][indexof(vertex2)] = weight
        end
    end

    return dict
end



weight(dict::Dict{UInt64,Dict{UInt64,Int}},index1::UInt64,index2::UInt64) = dict[index1][index2]

woclass · 2020 年3 月 5 日 08:40

可以看看 JuliaGraphs 的 repo

我把你的代码改了一下，加了点 julia 的语法糖。可以用一些更方便的写法。
例如

julia> g = Graph(false, :a,:b)
Graph{Symbol} vertexs = 2; edges = 0
[:a] White [no edge]
[:b] White [no edge]
julia> :a in g
true

julia> g = Graph(true, 1:5)
Directed Graph{Int64} vertexs = 5; edges = 0
[1] White [no edge]
[2] White [no edge]
[3] White [no edge]
[4] White [no edge]
[5] White [no edge]

julia> g[1, 2] = 1;
julia> g[2, 3] = 2;
julia> g[5, 2] = 3;
julia> g[1, 5] = 4;
julia> g
Directed Graph{Int64} vertexs = 5; edges = 4
[1] White =(1)=> [2] White
[1] White =(4)=> [5] White
[2] White =(2)=> [3] White
[3] White [no edge]
[4] White [no edge]
[5] White =(3)=> [2] White

julia> g[1]
[1] White =(1)=> [2] White
[1] White =(4)=> [5] White

julia> Vertex(1)
[1] White

julia> Vertex(:A)
[:A] White

julia> Vertex("node 1")
["node 1"] White

数据结构上面

Vertex{T} 只保留了 name 和 color 字段，name 完全可以替代掉 index；hop 貌似完全没用上
Graph{T} 的 list::Set{AdjList{T}} 改用 list::Vector{AdjList{T}} 了，看不出 Set 的必要

graph.jl

# graph.jl
# include("list.jl")
# import .LinkedList: Queue, push, remove, @lengthof
# 并没有用到以上函数

#--------------------------------#
#            vertex              #
#--------------------------------#

"""
    @enum Color begin
        White = 0
        Grey
        Black
    end

代顶点边是否访问过
+ `White` 未访问
+ `Grey`
+ `Black` 已访问
"""
@enum Color begin
    White = 0
    Grey
    Black
end
# @enum Color White=0 Grey=1 Black=2

"""
    mutable struct Vertex{T}
        name  :: T
        color :: Color
    end
    Vertex(name::T)

顶点 Vertex{T}
+ `name::T` 顶点代号，建议使用 :keyword、"String"、或 Integer
+ `color::Color` 顶点访问状态
"""
mutable struct Vertex{T}
    # value::T
    name::T
    color::Color
    # index::UInt64 # 直接使用 name
    # hop::Int # 貌似没用上

    function Vertex{T}(name::T) where T
        # new(name, White, 0, 0)
        new(name, White)
    end
end
Vertex(name::T) where T = Vertex{T}(name) # 自动推断类型参数 T
Base.show(io::IO, v::Vertex) = # 美化输出
    print(io, "[$(repr(v.name))] $(v.color)")

"名字作为唯一标识符"
Base.:(==)(vertex1::Vertex{T}, vertex2::Vertex{T}) where T =
    vertex1.name == vertex2.name

# valueof(vertex::Vertex{T}) where T = vertex.value
nameof(vertex::Vertex) = vertex.name

# indexof(vertex::Vertex) = vertex.index
# setindex(vertex::Vertex, index::UInt64) = vertex.index=index
visited!(vertex::Vertex) = vertex.color = Black
isvisted(vertex::Vertex) = !(notvisited(vertex))
notvisited(vertex::Vertex) = vertex.color == White



#--------------------------------#
#            adjlist             #
#--------------------------------#

"边的类型。edge: (end_point, weight)"
const Edge{T} = Tuple{Vertex{T}, Int}

"""
    mutable struct AdjList{T}
        vertex :: Vertex{T}
        edges  :: Vector{Edge{T}}
    end
    Edge{T} = Tuple{Vertex{T}, Int}
    AdjList(name::T)

邻接表节点 AdjList{T}
"""
mutable struct AdjList{T}
    vertex::Vertex{T}
    # edge::Set{Tuple{Vertex{T},Int}}
    edges::Vector{Edge{T}}

    function AdjList{T}(name::T) where T
        new(Vertex(name), Vector{Edge{T}}())
    end
end
# AdjList{T}(value::T) where T = AdjList{T}(Vertex{T}(value),Set{Tuple{Vertex{T},Int}}())
AdjList(name::T) where T = AdjList{T}(name)
function Base.show(io::IO, adjlist::AdjList)
    v0 = adjlist.vertex
    if isempty(adjlist.edges)
        println(io, "$v0 [no edge]")
    else
        for (v, w) in adjlist.edges
            println(io, "$v0 =($w)=> $v")
        end
    end
end

# Base.iterate(adjlist::AdjList{T}) where T = (adjlist.vertex,adjlist.edges)
vertexof(adjlist::AdjList) = adjlist.vertex
edgesof(adjlist::AdjList)  = adjlist.edges



#--------------------------------#
#             graph              #
#--------------------------------#
"""
    mutable struct Graph{T}
        vcount :: Int
        ecount :: Int
        list   :: Vector{AdjList{T}}
        hasdirection :: Bool
    end
    Graph{T}(has_direction=true)

图 Graph{T}
+ `vcount` 顶点数
+ `ecount` 边数
+ `list`   邻接表
+ `hasdirection` 是否有向
"""
mutable struct Graph{T}
    vcount::Int
    ecount::Int
    # list::Set{AdjList{T}}
    list::Vector{AdjList{T}}
    hasdirection::Bool

    function Graph{T}(direct::Bool=true) where T
        new(0, 0, Vector{AdjList{T}}(), direct)
    end
end
# Graph{T}(direct=true) where T = Graph{T}(0,0,Set{AdjList{T}}(),direct)
function Base.show(io::IO, g::Graph{T}) where T
    print(io, (g.hasdirection ? "Directed " : "") * "Graph{$T} ")
    print(io, "vertexs = $(g.vcount); edges = $(g.ecount)\n")
    if isempty(g.list)
        println(io, "[empty]")
    else
        for adj in g.list
            print(io, adj)
        end
    end
end

"返回 name 对应的顶点开头的邻接表 AdjList"
function Base.getindex(graph::Graph{T}, names::T) where T
    # 便于使用
    for current in graph.list # current::AdjList
        if names == nameof(vertexof(current))
            return current
        end
    end
    nothing
end

# vertexof(graph::Graph{T},index::UInt64) where T =
#     begin
#         for current in graph.list
#             if indexof(current.vertex) == index
#                 return current.vertex
#             end
#         end
#     end
"返回 name 对应的顶点"
vertexof(graph::Graph{T}, name::T) where T =
    vertexof(graph[name])

# getadjlist(graph::Graph{T},index::UInt64) where T = begin
#     for current in graph.list #AdjList
#         if indexof(vertexof(current)) == index
#             return current
#         end
#     end
# end
"返回 name 对应的顶点开头的邻接表 AdjList"
getadjlist(graph::Graph{T}, name::T) where T = graph[name]



#--------------------------------#
#           function             #
#--------------------------------#

# function edgesof(graph::Graph, index::UInt64)
#     adjlist = getadjlist(graph, index)
#     if adjlist != nothing
#         adjlist.edges
#     end
# end
"返回 name 对应顶点开头的边"
edgesof(graph::Graph{T}, name::T) where T = edgesof(graph[name])

# edgeof(adjlist::AdjList{T}) where T = adjlist.edge
# 前移至 AdjList 定义处

"辅助函数"
Base.in(name::T, graph::Graph{T}) where T =
    getadjlist(graph, name) != nothing

"""
    append_vertex!(graph::Graph{T}, name::T) where T
"""
# function append_vertex!(graph::Graph{T},value::T) where T
function append_vertex!(graph::Graph{T}, names::T...) where T
    # for adjlist in graph.list #AdjList
    #     if value == valueof(vertexof(adjlist))
    #         return
    #     end
    # end
    for name in names
        (name in graph) && return

        new_elmt = AdjList(name)
        # index = hash(name)
        # setindex(vertexof(new_elmt),index)
        push!(graph.list, new_elmt)
        graph.vcount += 1
        # index
    end
end
function Graph(direct::Bool, names::T...) where T
    graph = Graph{T}(direct)
    append_vertex!(graph, names...)
    graph
end
Graph(direct::Bool, r::UnitRange{T}) where T<:Integer =
    Graph(direct::Bool, collect(r)...)

#-------------------------#
# add egde with two index #
#-------------------------#

"""
    append_edge!(
        graph::Graph{T},
        index1::UInt64,
        index2::UInt64,
        w::Int=0
    ) where T

w: 权重
"""
# function append_edge!(graph::Graph{T},index1::UInt64,index2::UInt64,w::Int=0) where T
function append_edge!(
        graph::Graph{T},
        name1::T,
        name2::T,
        w::Int=0
    ) where T
    # judge that if index1 and index2 is in each vertex of graph.list(AdjList)
    adjlist1 = getadjlist(graph, name1)
    adjlist2 = getadjlist(graph, name2)
    # if adjlist1 == nothing || adjlist2 == nothing
    #     return
    # end
    name1 ∉ graph || name2 ∉ graph && return

    if graph.hasdirection
        push!(edgesof(adjlist1), (vertexof(adjlist2),w))
    else
        push!(edgesof(adjlist1), (vertexof(adjlist2),w))
        push!(edgesof(adjlist2), (vertexof(adjlist1),w))
    end

    graph.ecount += 1
end

"graph[:a, :b] = weight"
Base.setindex!(graph::Graph{T}, w::Int, name1::T, name2::T) where T =
    append_edge!(graph, name1, name2, w)

load_weight.jl

# load_weight.jl
# include("graph2.jl")

# function load_weight(graph::Graph{T}) where T
function load_weight(graph::Graph{T}) where T
    # dict=Dict{UInt64,Dict{UInt64,Int}}()
    dict = Dict{Tuple{T,T}, Int}()

    for adjlist in graph.list # Set of AdjList |vertex,Set{Tuple}|
        vertex1, edges = vertexof(adjlist), edgesof(adjlist)
        # dict[indexof(vertex1)]=Dict{UInt64,Int}()
        for (vertex2, weight) in edges
            # dict[indexof(vertex1)][indexof(vertex2)] = weight
            name_tup = (nameof(vertex1), nameof(vertex2))
            dict[name_tup] = weight
        end
    end

    dict
end

# weight(dict::Dict{UInt64,Dict{UInt64,Int}},index1::UInt64,index2::UInt64) =
#     dict[index1][index2]

"dict[name1, name2]"
Base.getindex(
    dict::Dict{Tuple{T,T}, Int},
    name1::T, name2::T
) where T = dict[(name1, name2)]

dijkstra.jl

# dijkstra.jl
include("graph.jl")
include("load_weight.jl")

#--------------------------------#
#            Dijkstra            #
#--------------------------------#
# function dijkstra(graph::Graph{T},start::UInt64,last::UInt64) where T
function dijkstra(
        graph::Graph{T}, 
        start::T, 
        last::T
    ) where T
    weight = load_weight(graph)
    println("Weights:")
    for (k,v) in weight
        # println(k,'\t',v)
        println("  $k => $v")
    end

    # need a list for save
    # list=Dict{UInt64,Int}()
    distance = Dict{T, Int}()   # 记录各点到起点的最短距离
    # init distance
    for adjlist in graph.list
        vtx_name = adjlist |> vertexof |> nameof
        distance[vtx_name] = abs(typemax(Int)) # 初始化距离为 max
    end

    # 为起点 start 相连的点赋值 distance
    for (vertex, _) in edgesof(graph, start)
        vtx_name = nameof(vertex)
        distance[vtx_name] = weight[start, vtx_name]
        vertex.color = Grey # 访问过，但不确定是否最小
    end
    # 起点自身赋值
    vertexof(graph,start).color = Black

    # 从 Grey 开始
    for (minindex, _) in distance
        # if vertexof(graph, minindex).color == Grey
        Grey!=vertexof(graph, minindex).color && continue

        for (vertex, _) in edgesof(graph,minindex)
            # if vertex.color != Black
            Black==vertex.color && continue
            
            vtx_name = nameof(vertex)
            distance[vtx_name] = min(
                distance[vtx_name],
                distance[minindex] + weight[minindex, vtx_name]
            )
            vertex.color = Grey
            # end
        end
        vertexof(graph, minindex).color = Black
        # end
    end

    return distance[last]
end

# index = Vector{UInt64}(undef, 7)
# graph = Graph{Int}()
# for i in 1:7
#     index[i] = append_vertex!(graph,i)
# end
graph = Graph(true, 1:7)

# append_edge!(graph,index[1],index[2],2)
# append_edge!(graph,index[1],index[3],5)
# append_edge!(graph,index[2],index[4],1)
# append_edge!(graph,index[2],index[5],3)
# append_edge!(graph,index[3],index[2],6)
# append_edge!(graph,index[3],index[6],8)
# append_edge!(graph,index[4],index[5],4)
# append_edge!(graph,index[5],index[7],9)
# append_edge!(graph,index[6],index[7],7)
graph[1, 2] = 2
graph[1, 3] = 5
graph[2, 4] = 1
graph[2, 5] = 3
graph[3, 2] = 6
graph[3, 6] = 8
graph[4, 5] = 4
graph[5, 7] = 9
graph[6, 7] = 7

# graph[1, 2] = 2
# graph[1, 4] = 1
# graph[2, 4] = 3
# graph[2, 5] = 10
# graph[3, 1] = 4
# graph[3, 6] = 5
# graph[4, 3] = 2
# graph[4, 5] = 2
# graph[4, 6] = 8
# graph[4, 7] = 4
# graph[5, 7] = 6
# graph[7, 6] = 1
# res == 5

# res=dijkstra(graph,index[1],index[7])
# print(res)
res = dijkstra(graph, 1, 7)
println("shortest length: $res")

运行输出

Weights:
  (2, 5) => 3
  (5, 7) => 9
  (3, 6) => 8
  (1, 2) => 2
  (3, 2) => 6
  (2, 4) => 1
  (6, 7) => 7
  (1, 3) => 5
  (4, 5) => 4
shortest length: 14

julia> graph
Directed Graph{Int64} vertexs = 7; edges = 9
[1] Black =(2)=> [2] Black
[1] Black =(5)=> [3] Black
[2] Black =(1)=> [4] Grey
[2] Black =(3)=> [5] Black
[3] Black =(6)=> [2] Black
[3] Black =(8)=> [6] Black
[4] Grey =(4)=> [5] Black
[5] Black =(9)=> [7] Grey
[6] Black =(7)=> [7] Grey
[7] Grey [no edge]

ver: 1.0