    
   
  
   

ng i
Tính chtng i ngn nht
ng i ngn nht tmtnh
Thut toán Dijkstra
ng i ngn nht gia minh
Thut toán Floyd–Warshall
   a
Trong  thvô hng = ,
ng i
là dãy các nh , , … ,
2 nh liên tip,  c ni bi 1 cnh trong .
c gi là ng i tn
Chu trình
là ng i, , … , vi > 1
trong ónh u tiên phân bit và =
Vi thcó hng, trong mtng i hay
chu trình, 2 nh liên tip(, )phi là mt
cung thuc
  
 thcó hng = vi hàm trng s
cung . Trng scang i
cnh ngha:

Ví d: 
     a
ng i ngn nht (NN) tn là
ng i có trng snhnht tn .
Trng s ng i ngn nht tn
cnh ngha:
, = min : đườngđitừđến
Chú ý: , = ∞không tn ting i
tn.