Algorithm Tutorial: Graphs Part 3: Dijkstra's Algorithm, Weighted Shortest Paths

Apr 15, 2018 · Santa Clara, United States of America

Prerequisites: You should have a good understanding of the material from Graphs Part 1 and 2. In those sessions, we covered an introduction to what graphs are and how they are used to model problems, the distinction between weighted/unweighted and directed/undirected graphs, common graph representations (adjacency matrix, adjacency list), the definition of the shortest path problem with some example applications, and the BFS algorithm for finding unweighted shortest paths. We also saw a variety of problems that helped us build intuition about how to map problems to BFS. The new material builds on essentially everything above, so it is critical to have a good understanding of it before attending the session.

It follows naturally you should also have a good understanding of the previous material's prereqs: how to program, use basic big-O analysis, and use basic data types such as maps, sets, and lists.

Difficulty: 6.5/10

I will introduce Dijkstra's algorithm, a generalization of BFS that solves the *weighted* shortest path problem, and show a few nice problems that use it. I may also briefly mention some other path finding algorithms such as Bellman-Ford.

Event organizers
  • Tech Interviews and Competitive Programming

    Brush up on your technical problem solving skills together in a friendly environment where you can feel free to share your job search experiences and role-play a short series of practice coding interviews with a study partner in a relaxed setting.  This group is meant to allow participants to build up their self-confidence by solving a range problems from easy to challenging and become comfortable with working together on a problem on paper with another person. For more experienced members we also have wor

    Recent Events
    More

Are you organizing Algorithm Tutorial: Graphs Part 3: Dijkstra's Algorithm, Weighted Shortest Paths?

Claim the event and start manage its content.

I am the organizer
Social
Topics
Rating

based on 0 reviews