الگوریتم ارسال-برچسب

الگوریتم ارسال-برچسب (به انگلیسی: push–relabel algorithm) یکی از کارآمدترین الگوریتم‌ها برای محاسبهٔ یک مسئله بیشینه جریان است. الگوریتم عمومی دارای پیچیدگی زمانی  است، در حالی که پیاده‌سازی آن با قانون شیوهٔ رأس‌ها به صورت FIFO دارای زمان اجرای ، با شیوهٔ انتخاب فعال‌ترین رأس دارای پیچیدگی زمانی  و با پیاده‌سازی با کمک داده‌ساختار درخت پویای ترجان و اسلیتور دارای زمان اجرای  است. مجانباً این الگوریتم، از الگوریتم ادموند-کارپ که زمان اجرای آن  است کاراتر است.

تخلیه

راس سرشار u با push کردن همهٔ جریان‌های اضافی اش در میان یال‌های مجاز به رأس‌های همسایه تخلیه می‌شود. راس U اگر لازم باشد برچسب‌گذاری می‌شود.
کد تخلیهٔ راس سرشار مطابق زیر است:
DISCHARGE(u)
  while e[u]> ۰
      do v ← current[u]
         if v = NIL
       then RELABEL(u)
              current[u] ← head[N[u]]
          elseif cf(u, v)> 0 and h[u] = h[v] + 1
           then PUSH(u, v)
         else current[u] ← next-neighbor[v]

مثال

در شکل‌های زیر مثالی برای این الگوریتم آورده شده که توضیح آن آورده شده‌است.

 
در قسمت a شبکهٔ جریان‌ها قبل از اولین تکرار در حلقه نشان داده شده‌است.
۲۶ مقدار جریان از مبدأ s خارج شده در سمت راست فهرست L که شامل همهٔ رأس‌ها غیر از مبدأ و مقصد است نشان داده شده که در حالت اول راس u را x می‌گیریم زیر هر راس در فهرست L رأس‌های همسایه قرار داده شده‌است. راس x تخلیه می‌شود به ارتفاع ۱ برچسب‌گذاری می‌شود. ۵ واحد از جریان اضافی به  y داده می‌شود. و ۷ مقدار باقی‌مانده به T وارد می‌شود. x برچسب‌گذاری شده پس به سر فهرست باز می‌گردد. در قسمت b پس از x راس بعدی که تخلیه می‌شود راس y است شکل عمل تخلیهٔ y را با جرئیات نشان داده. y برچسب‌گذاری شده پس دوباره به سر فهرست می‌آید. در قسمت y x , c را در فهرست دنبال می‌کند.
پس راس x دوباره تخلیه می‌شود x برچسب‌گذاری نمی‌شود پس در فهرست باقی می‌ماند و به سر فهرست نمی‌آید. در قسمت d راس z راس x را دنبال می‌کند پس تخلیه می‌شود و به ارتفاع ۱ برچسب‌گذاری می‌شود و همهٔ ۸ مقدارش به راس t می‌رود سپس به ابتدا ی فهرست l می‌رود چرا که برچسب‌گذاری شده حال در قسمت e راس y راس z را دنبال می‌کند پس راس y باید تخلیه شود ولی چون هیچ جریان اضافی ندارد راس x تخلیه می‌شود و y سر جایش در فهرست باقی می‌ماند.
ولی چون x هم جریانی ندارد آن هم در فهرست می‌ماند و این الگوریتم به  ته فهرست L می‌رسد و تمام می‌شود. هیچ راسی با جریان اضافی نداریم پس جریان بالا بیشینه جریان است. به همین ترتیب توسط الگوریتم بالا بیشینه شاره را با زمان  پیدا کردیم.

پیاده‌سازی نمونه

پیاده‌سازی با پایتون:
  def relabel_to_front(C, source, sink):
     n = len(C) # C is the capacity matrix
     F = [[0] * n for _ in xrange(n)]
     # residual capacity from u to v is C[u][v] - F[u][v]

     height = [0] * n # height of node
     excess = [0] * n # flow into node minus flow from node
     seen   = [0] * n # neighbours seen since last relabel
     # node "queue"
     list   = [i for i in xrange(n) if i != source and i != sink]

     def push(u, v):
         send = min(excess[u], C[u][v] - F[u][v])
         F[u][v] += send
         F[v][u] -= send
         excess[u] -= send
         excess[v] += send

     def relabel(u):
         # find smallest new height making a push possible,
         # if such a push is possible at all
         min_height = ∞
         for v in xrange(n):
             if C[u][v] - F[u][v]> 0:
                 min_height = min(min_height, height[v])
                 height[u] = min_height + 1

     def discharge(u):
         while excess[u]> 0:
             if seen[u] <n: # check next neighbour
                 v = seen[u]
                 if C[u][v] - F[u][v]> 0 and height[u]> height[v]:
                     push(u, v)
                 else:
                     seen[u] += 1
             else: # we have checked all neighbours. must relabel
                 relabel(u)
                 seen[u] = 0

     height[source] = n   # longest path from source to sink is less than n long
     excess[source] = Inf # send as much flow as possible to neighbours of source
     for v in xrange(n):
         push(source, v)

     p = 0
     while p <len(list):
         u = list[p]
         old_height = height[u]
         discharge(u)
         if height[u]> old_height:
             list.insert(0, list.pop(p)) # move to front of list
             p = 0 # start from front of list
         else:
             p += 1

     return sum(F[source])
توجه داشته‌باشید که پیاده‌سازی بالا چندان کارآمد نیست. این پیاده‌سازی از الگوریتم ادموند-کارپ حتی برای گراف‌های پرتراکم کندتر است.