hkucuk

Алгоритм кратчайшего пути Дейкстры

14 апреля 2022 г. • ☕️ 3 мин чтение • 🏷 компьютер, программное, алгоритм

Переведено автором: Deutsch • English • Italiano • Русский


Алгоритм кратчайшего пути Дейкстры с одним источником — это алгоритм поиска кратчайшего возможного пути от одной начальной точки ко всем другим точкам на графе. Этот алгоритм используется для поиска кратчайшего пути между всеми точками за заданное время.

Принцип работы алгоритма следующий:

  1. Расстояние до начальной точки установлено равным 0, а расстояние до всех других точек установлено равным INF (т.е. бесконечно).
  2. Обходятся все точки на графике и находится кратчайшая точка без расстояния (INF). Эта точка посещается, и расстояние до нее обновляется.
  3. Также обновляются расстояния до других точек, с которыми связана посещаемая точка. Например, если расстояние до посещенной точки равно X, а до другой точки, связанной с этой точкой, есть расстояние Y, то расстояние до этой другой точки будет равно X+Y.
  4. Этот шаг повторяется, и точка без кратчайшего расстояния посещается, и расстояние до нее обновляется. Этот шаг продолжается до тех пор, пока не будут посещены все точки.

Таким образом, алгоритм находит кратчайший путь между всеми точками.

Алгоритм Дейкстры имеет одну большую слабость: он не обрабатывает линии с отрицательным весом. Алгоритм Дейкстры предполагает, что веса взвешенных линий неотрицательны. Поэтому он не обрабатывает линии с отрицательным весом и не дает точных результатов.

Вот код алгоритма на 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)
}

Когда программа будет запущена, вывод будет следующим.

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

Код алгоритма на PHP выглядит следующим образом:

<?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);

Ресурсы