In Part 1 we covered what graphs are and how to represent them. In Part 2 we explored BFS and DFS — the two ways to traverse a graph. Now it’s time for the advanced algorithms that solve real engineering problems: finding the shortest weighted path, connecting a network at minimum cost, and efficiently grouping nodes. This is Part 3 of a 3-part series. Start from Part 1 if you’re new to graphs. Dijkstra’s Algorithm — Shortest Path in a Weighted Graph The Problem BFS finds the shortest path in an unweighted graph (fewest edges). But what if edges have READ MORE
Tag: shortest path
Dijkstra’s Algorithm Shortest Path
Dijkstra’s algorithm is the most popular algorithm to find the shortest paths from a certain vertex in a weighted graph.In fact, the algorithm will find the shortest paths to every vertex from the start vertex.The algorithm takes both greedy and dynamic programming approach that it will try to find local optimum paths first and use them to find the shortest paths.Let’s take a look at how it works! How does Dijkstra’s algorithm work? Let’s say we need to find the shortest path from node A to node E. There are five nodes and each edge is weighted with the cost READ MORE