Problem najšireg puta — разлика између измена

 

Ako su težine svih grana neusmerenog grafa pozitivne, onda minimax udaljenost između parova tačaka (maksimalna težina ivica minimax puta) formira ultrametrički prostor (specijalna vrsta [[metrički prostor|metričkog prostora]]); obrnuto svaki konačan ultrametrički prostor dolazi od minimax udaljenosti. Struktura podataka formirana od minimalnog razapinjućeg stabla dozvoljava da minimax udaljenost između bilo kog para čvorova bude izračunata za konstantno vreme u zavisnosti od udaljenosti, koristeći najmanjeg zajedničkog pretka u [[Dekartovo stablo|Dekartovom stablu]] ([[binarno stablo]]). Koren Dekartovog stabla predstavlja najtežu granu minimalnog razapinjućeg stabla, i deca korena su Dekartova stabla koja su rekurzivno formirana od podstabla minimalnog razapinjućeg stabla formiranog uklanjanjem najtežih grana. Listovi Dekartovog stabla predstavljaju čvorove ulaznog grafa, a minimax rastojanje između dva čvora je jednako težini čvora koji je najmanji zajednički predak Dekartovog stabla. Jednom kad je minimalno razapinjuće stablo sortirano, Dekartovo stablo se može konstruisati za linearno vreme.

 

== Usmereni grafovi ==

| volume = 29

|year=2004}}</ref>

 

== Reference ==