大家觉得SPFA怎么样？

wgtiyg · 发表于 2014-11-5 16:35:58

忽略段工的长相，只说说SPFA。大家有什么见解？

备选：
a) 踩
b) 穿钉鞋踩

顺手贴段 F 代码（也请大虾挑错）

[Fortran] 纯文本查看 复制代码

Program Spfa
  Integer Wei(100, 100)
  Integer Way(100)
  Integer Queue(100)
  Logical Visit(100)
  Read *, Nvert, Nedge, Mfrom, Mto
  Do I = 1, Nedge
    Read *, Lposx, Lposy, Lwei
    Wei(Lposx, Lposy) = Lwei
    Wei(Lposy, Lposx) = Lwei
  End Do
  Do I = 1, Nedge
    Way(I) = Huge(I)
    Visit(I) = .False.
  End Do
  Queue(1) = Mfrom
  Visit(Mfrom) = .True.
  Way(Mfrom) = 0
  Jqh = 1
  Jqt = 2
  Do
    If (Jqh==Jqt) Go To 7
    Icurr = Queue(Jqh)
    Jqh = Jqh + 1
    If (Jqh==101) Jqh = 1
    Visit(Icurr) = .False.
    Do I = 1, Nvert
      If (Wei(Icurr,I)>0 .And. Wei(Icurr,I)+Way(Icurr)<Way(I)) Then
        Way(I) = Way(Icurr) + Wei(Icurr, I)
        If (.Not. Visit(I)) Then
          Visit(I) = .True.
          Queue(Jqt) = I
          Jqt = Jqt + 1
          If (Jqt==101) Jqt = 1
        End If
      End If
    End Do
  End Do
7 Print *, Way(Mto)
End