On the dijkstra’s algorithm, each edge on the graph has a number associated with it - which is called its' weight.
A weighted graph is a way to assign weight to some graph’s edges.
An unweighted graph is a graph with no weights.
Breath-first search find you the path with the fewest nodes (shortest path) on an unweighted graph.
To get the shortest path on a weighted graph you must use the dijkstra’s algorithm.
The dijkstra’s algorithm has 4 steps: . Find the cheapest node (with the lesser weight) . Update the costs of the neighbor of this node . Repeat until done for each node in the graph . Calculate the final path.
Graphs can have cycles: You start on a node, travel to others and come back to that node.
Following a cycle on a weighted graph will never give you the shortest path.
An undirected graph (with no direction between 2 nodes) means that 2 nodes point to each other.
Dijktra’s algorithm has 2 conditions to be applied:
To implement the dijkstra’s algorithm, you need a table with the cost of each node. This table also needs to have the parent of all nodes, where the last value on the “cost” column is always updated. E.g.:
Parent | Node | Cost
Book | LP | 5
Book | Poster | 0
Poster | Guitar | 30 35
The Dijkstra’s algorith can no only be applied for calculating distances, but also when you need to minimize something. E.g. when you need to minimize the amount of money to spend when you have different options to buy products.
Graphs with negative weight edges break dijkstra’s algorithm.
To find the shortest path in a graph with negative-weight edges, you can use the Bellman-Ford algorithm (since they break dijkstra’s).