Generic Labeling methods

anchored to [[111.00_anchor]]

convenient generalization of Dijkstra and Bellman-Ford::

• for each vertex, maintain some sort of status variable S(v) in (unreachable, labelchanged,settled) >> marking their current status for further use
• Repeatedly relax edges >> updating their status variable
• Do this until nothing changes any more - we reached a status of everything being finite ![[Pasted image 20221118111205.png]]

Principle acts as blueprint for labeling and traversing through graphs and their vertices..

• a vertex could be scanned several times and change its status often
• the quantity of those scans and changes depends on line 8 of the code >> how the vertex is picked
• if managed to select a vertex v ==such that== v.dist is already the correct distance, then we scan each vertex once at max >> optimal solution
• Dijkstras algorithm is a special case of labeling method :
  • one can show that if we choose the vertex that has the smallest distance value among all verties with status “labelchanged” then the algorithm is equiv to DIjkstra and each vertex gets scanned at most once.