Shortest-Path Algorithm

Shortest-Path Algorithm is an algorithm that calculate the shortest path of one vertex to all other vertices in a #202204112118. The path could be unweighted or weighted. It is similar to level-order traversal. Sometimes, it is wise to 202204151111# in order to store path information for later usage.

There are several algorithms to handle different cases:

202204151055# for unweighted graph
202204151059# for weighted graph when there are no negative weight
202204151151# for weighted graph where there could be negative weight
202204200949# for known acyclic graph

Links to this page

Unweighted Shortest Path

To calculate the #shortest path for unweighted graph, the following algorithm used the strategy breadth-first search where the siblings of the vertex get searched first which utilise the 202112101836.
Directed Graph

To calculate the shortest path for each vertex to each other vertices, see 202204141149#.
Dijkstra’s Algorithm

Dijkstra’s Algorithm is a #202204151143 to find the #shortest path for weighted graph.
Create A Table for Shortest Path Algorithm

The following algorithm is used to initialise a table structure for #202204141149 in order to store current calculated information.
Common Problem in Finding Longest or Shortest Path in Non-acyclic Graph

In #finding the shortest path, it is quite easy to get into the so called negative-cost cycles, where one could stay in a loop forever if there is a negative weight edge in the graph.

#algorithm #graph