# Lecture 16: Dijkstra | Summary and Q&A

297.5K views
January 14, 2013
by
MIT OpenCourseWare
Lecture 16: Dijkstra

## TL;DR

Dijkstra's Algorithm is a greedy algorithm that finds the shortest path in a graph, starting from a given vertex and considering positive weights for the edges.

## Install to Summarize YouTube Videos and Get Transcripts

### Q: What is Dijkstra's Algorithm?

Dijkstra's Algorithm is a greedy algorithm that finds the shortest path in a graph, starting from a given vertex and considering positive weights for the edges.

### Q: What is the process of relaxation in Dijkstra's Algorithm?

Relaxation is the process of updating the length of the current shortest path by considering an alternative path. It is done by comparing the current path length with the sum of the path length from the source vertex to another vertex and the weight of the edge.

### Q: Can Dijkstra's Algorithm handle negative edges?

No, Dijkstra's Algorithm cannot handle negative edges. It assumes that all edge weights are positive or zero.

### Q: How does Dijkstra's Algorithm work for directed acyclic graphs (DAGs)?

Dijkstra's Algorithm can be applied to DAGs to find the shortest paths. The algorithm starts by topologically sorting the graph and then iterates through the vertices in the sorted order, relaxing the outgoing edges.

## Summary & Key Takeaways

• Dijkstra's Algorithm is a concrete algorithm for finding shortest paths in a graph.

• It uses the concept of relaxation, which is the process of updating the length of current shortest paths.

• The algorithm works by iterating through the vertices and relaxing the edges, finding the shortest paths gradually.