174
правки
Изменения
→Псевдокод
== Псевдокод ==
'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>
<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)
'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()
'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)
<tex>M_0</tex>.add(u)
== Сложность ==
