Arborele celor mai scurte căi

Această intrare pe tema programării este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia .

Cel mai scurt arbore de cale al unui vârf specific ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">v</span></span>}}${\ displaystyle v} a unui grafic ponderat ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">G.</span></span>}}${\ displaystyle G} , este un subgraf și un copac ale cărui vârfuri sunt toate de la care se poate ajunge ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">v</span></span>}}${\ displaystyle v} în ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">G.</span></span>}}${\ displaystyle G} iar arcadele sunt reduse astfel încât singura cale prezentă între ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">v</span></span>}}${\ displaystyle v} și orice alt nod al graficului este calea cea mai scurtă .

Dacă graficul ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">G.</span></span>}}${\ displaystyle G} arborele cu cea mai scurtă cale este conectat este un subgraf care se întinde. Cel mai scurt arbore de cale are adesea noduri etichetate cu costul total al celei mai scurte căi pentru a ajunge la acel nod începând de la nodul rădăcină ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">v</span></span>}}${\ displaystyle v} .

Cel mai scurt arbore de căi este adesea generat de algoritmi de căutare de cale mai scurte ca suport, chiar dacă este necesară o singură cale mai scurtă între două noduri specifice.

Elemente conexe

• Mod minim
• Algoritm de căutare
• Algoritmul lui Dijkstra

Portal IT

Portalul de matematică