Shortest Path in a Graph: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 10: Line 10:


=The Problem=
=The Problem=
The '''single-source shortest paths''' is formally defined as follows: given a '''directed''' graph G=(V, E) , with n = │V│ and m=│E│, where each edge has a '''non-negative''' length ℓ<sub>e</sub>, and a [[Graph_Concepts#Source_Vertex|source vertex]] s, compute for
The '''single-source shortest paths''' is formally defined as follows: given a '''directed''' graph G=(V, E) , with n = │V│ and m=│E│, where each edge e has a '''non-negative''' length ℓ<sub>e</sub>, and a [[Graph_Concepts#Source_Vertex|source vertex]] s, compute for


=Shortest Path Algorithms=
=Shortest Path Algorithms=
* [[Breadth-First Search-based Shortest Path Algorithm]]
* [[Breadth-First Search-based Shortest Path Algorithm]]
* [[Dijkstra's Shortest-Path Algorithm]]
* [[Dijkstra's Shortest-Path Algorithm]]

Revision as of 19:44, 14 October 2021

External

Internal

Overview

There are several algorithms that compute the shortest path between two vertices in a graph, and they can be used or not depending on the characteristics of the graph, such as whether is directed or undirected, the edges have weights, the weights are negative or not.

The Problem

The single-source shortest paths is formally defined as follows: given a directed graph G=(V, E) , with n = │V│ and m=│E│, where each edge e has a non-negative length ℓe, and a source vertex s, compute for

Shortest Path Algorithms