Last weeks have been a bit slow on the algorithm front. Still on it though. I have been solving some Graph challenges on www.hackerrank.com and reading several different texts on Dijkstra's search algorithm.
It seems like this is an algorithm that is a bit tough to understand and implement in a correct and efficient way. Dijkstra's algorithm can be used on graphs with weighted edges, i.e. different paths have different costs. As long as the weights have positive values Dijkstra's algorithm should work fine.
The procedure is quite similar to Breadth First Search, the difference here being that the total edge weight can be less even when more edges are involved. It is therefore necessary to keep track of the current total, and if a shorter path is found, update the total and the parent node (can be used for printing the vertices visited when traveling the shortest distance from vertex v1 to vertex v2).
Dijkstra's algorithm is also greedy, in the sense that it visits the vertices along the current shortest path first. This can be achieved using a priority queue to efficiently select the vertex with the lowest total weight currently.
I will do an attempt to implement Dijkstra's algorithm in an optimal way using a Fibonacci heap for priority queue
It seems like this is an algorithm that is a bit tough to understand and implement in a correct and efficient way. Dijkstra's algorithm can be used on graphs with weighted edges, i.e. different paths have different costs. As long as the weights have positive values Dijkstra's algorithm should work fine.
The procedure is quite similar to Breadth First Search, the difference here being that the total edge weight can be less even when more edges are involved. It is therefore necessary to keep track of the current total, and if a shorter path is found, update the total and the parent node (can be used for printing the vertices visited when traveling the shortest distance from vertex v1 to vertex v2).
Dijkstra's algorithm is also greedy, in the sense that it visits the vertices along the current shortest path first. This can be achieved using a priority queue to efficiently select the vertex with the lowest total weight currently.
I will do an attempt to implement Dijkstra's algorithm in an optimal way using a Fibonacci heap for priority queue
Kommentarer
Skicka en kommentar