hkucuk

Algoritmo del percorso più breve di Dijkstra

14 aprile 2022 • ☕️ 3 min leggi • 🏷 computer, software, algoritmo, grafico

Tradotto dall'autore in: Deutsch • English • Italiano • Русский


L’algoritmo del percorso più breve a sorgente singola di Dijkstra è un algoritmo per trovare i percorsi più brevi possibili da un punto di partenza a tutti gli altri punti su un grafico. Questo algoritmo viene utilizzato per trovare il percorso più breve tra tutti i punti in un dato tempo.

Il principio di funzionamento dell’algoritmo è il seguente:

  1. La distanza del punto iniziale è impostata su 0 e la distanza di tutti gli altri punti è impostata su INF (cioè infinito).
  2. Vengono attraversati tutti i punti del grafico e viene trovato il punto più corto senza distanza (INF). Questo punto viene visitato e la sua distanza viene aggiornata.
  3. Vengono aggiornate anche le distanze di altri punti a cui è collegato il punto visitato. Ad esempio, se la distanza del punto visitato è X e c’è una distanza Y da un altro punto collegato a questo punto, la distanza di quest’altro punto sarà X+Y.
  4. Questo passaggio viene ripetuto e viene visitato il punto senza la distanza più breve e la sua distanza viene aggiornata. Questo passaggio continua fino a quando tutti i punti sono stati visitati.

L’algoritmo trova quindi il percorso più breve tra tutti i punti.

L’algoritmo di Dijkstra ha un grosso punto debole, non gestisce le linee pesate negativamente. L’algoritmo di Dijkstra presuppone che i pesi delle linee pesate non siano negativi. Pertanto, non gestisce le linee pesate negativamente e non fornisce risultati accurati.

Ecco il codice per l’algoritmo in GoLang:

package main

import "fmt"

const INF = int(^uint(0) >> 1)

type Graph [][]int

func dijkstra(g Graph, source int) []int {
	distances := make([]int, len(g))
	for i := range distances {
		distances[i] = INF
	}
	distances[source] = 0

	visited := make([]bool, len(g))

	for i := 0; i < len(g); i++ {
		minDistance := INF
		var minNode int
		for j := range g {
			if !visited[j] && distances[j] < minDistance {
				minDistance = distances[j]
				minNode = j
			}
		}
		visited[minNode] = true

		for j, cost := range g[minNode] {
			if cost != 0 {
				if minDistance+cost < distances[j] {
					distances[j] = minDistance + cost
				}
			}
		}
	}

	return distances
}

func main() {
	g := Graph{
		{0, 3, 0, 2, 0},
		{3, 0, 5, 0, 6},
		{0, 5, 0, 4, 0},
		{2, 0, 4, 0, 1},
		{0, 6, 0, 1, 0},
	}
	distances := dijkstra(g, 0)
	fmt.Println(distances)
}

Quando il programma viene eseguito, l’output sarà il seguente.

> go run main.go                   
[0 3 6 2 3]

Il codice dell’algoritmo in PHP è il seguente:

<?php

const INF = PHP_INT_MAX;

$graph = [
    [0, 3, 0, 2, 0],
    [3, 0, 5, 0, 6],
    [0, 5, 0, 4, 0],
    [2, 0, 4, 0, 1],
    [0, 6, 0, 1, 0],
];

$source = 0;
$distances = array_fill(0, count($graph), INF);
$distances[$source] = 0;

$visited = array_fill(0, count($graph), false);

for ($i = 0; $i < count($graph); $i++) {
    $minDistance = INF;
    $minNode = -1;
    for ($j = 0; $j < count($graph); $j++) {
        if (!$visited[$j] && $distances[$j] < $minDistance) {
            $minDistance = $distances[$j];
            $minNode = $j;
        }
    }
    $visited[$minNode] = true;

    for ($j = 0; $j < count($graph); $j++) {
        if ($graph[$minNode][$j] != 0) {
            if ($minDistance + $graph[$minNode][$j] < $distances[$j]) {
                $distances[$j] = $minDistance + $graph[$minNode][$j];
            }
        }
    }
}

print_r($distances);

Risorse