MODULE Algorithms

  USE Data_Structures

  IMPLICIT NONE

CONTAINS

  ! Bellman-Ford algoritmus
  TYPE(List) FUNCTION Bellman_Ford(g, source, destination)
    IMPLICIT NONE

    TYPE(Graph), INTENT(IN) :: g                  ! A gráf, amiben keresünk
    INTEGER, INTENT(IN) :: source, destination    ! A keresett út végpontjai

    INTEGER, DIMENSION(1:2) :: boundaries
    INTEGER, ALLOCATABLE :: parent(:)
    REAL, ALLOCATABLE :: distance(:)
    INTEGER :: num, i, j, u, v
    TYPE(Node), POINTER :: p
    TYPE(Edge) :: e

    boundaries = Vertex_Boundaries(g)
    num = boundaries(2)-boundaries(1)+1
    ALLOCATE(parent(num))
    ALLOCATE(distance(num))

    DO i = 1, num
      parent(i) = -1
      distance(i) = HUGE(1.0)
    END DO

    distance(source-boundaries(1)+1) = 0

    DO j = 1, num-1
      p => g%edges%l%first
      DO WHILE (ASSOCIATED(p))
        IF (distance(p%data%source-boundaries(1)+1) + p%data%weight < &
            distance(p%data%destination-boundaries(1)+1)) THEN
          distance(p%data%destination-boundaries(1)+1) = &
            distance(p%data%source-boundaries(1)+1) + p%data%weight
          parent(p%data%destination-boundaries(1)+1) = &
            p%data%source-boundaries(1)+1
        END IF
        p => p%next
      END DO
    END DO

    CALL Initialize_List(Bellman_Ford)

    v = destination-boundaries(1)+1
    DO WHILE (v /= source-boundaries(1)+1)
      IF (parent(v) == -1) THEN
        CALL Initialize_List(Bellman_Ford)
        RETURN
      END IF
      u = parent(v)
      e = Create_Edge(u+boundaries(1)-1, v+boundaries(1)-1, &
                      Weight_Of(g, u+boundaries(1)-1, v+boundaries(1)-1))
      CALL Push_Front(Bellman_Ford, e)
      v = u
    END DO
  END FUNCTION Bellman_Ford

END MODULE Algorithms