hkucuk

Dijkstra’s Shortest Path Algorithm

April 14, 2022 • ☕️ 3 min read • 🏷 computer, software, algorithm, graph

Translated by author into: Deutsch • English • Italiano • Русский


Dijkstra’s single-source shortest path algorithm is an algorithm for finding the shortest possible paths from one starting point to all other points on a graph. This algorithm is used to find the shortest path between all points in a given time.

The working principle of the algorithm is as follows:

  1. The distance of the starting point is set to 0 and the distance of all other points is set to INF (ie infinite).
  2. All points on the graph are traversed and the shortest point with no distance (INF) is found. This point is visited and its distance is updated.
  3. The distances of other points to which the visited point is connected are also updated. For example, if the distance of the visited point is X and there is a distance Y to another point connected to this point, the distance of this other point will be X+Y.
  4. This step is repeated and the point with no shortest distance is visited and its distance is updated. This step continues until all points have been visited.

The algorithm thus finds the shortest path between all points.

Dijkstra’s algorithm has one major weakness, it does not handle negatively weighted lines. Dijkstra’s algorithm assumes that the weights of the weighted lines are not negative. Therefore, it does not handle negatively weighted lines and does not give accurate results.

Here is the code for the algorithm 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)
}

When the program is run, the output will be as follows.

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

The code of the algorithm in PHP is as follows:

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

Resources