[go: up one dir, main page]
Scribd
Upload
47 views7 pages

Algo Dijkstra Basics Typed

Dijkstra's algorithm is used to find the shortest path between a source node and all other nodes in a graph. It works by maintaining two sets: the set of nodes whose shortest path from the source is already determined, and everything else. It iteratively selects the node with the minimum tentative distance and updates the distances of its neighbors if a shorter path is found, until all nodes are processed. Dijkstra's algorithm runs in O(m+n log n) time for a graph with n nodes and m edges. It finds shortest paths in graphs with non-negative edge lengths but not graphs with negative edge lengths.

Uploaded by

tj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
47 views7 pages

Algo Dijkstra Basics Typed

Dijkstra's algorithm is used to find the shortest path between a source node and all other nodes in a graph. It works by maintaining two sets: the set of nodes whose shortest path from the source is already determined, and everything else. It iteratively selects the node with the minimum tentative distance and updates the distances of its neighbors if a shorter path is found, until all nodes are processed. Dijkstra's algorithm runs in O(m+n log n) time for a graph with n nodes and m edges. It finds shortest paths in graphs with non-negative edge lengths but not graphs with negative edge lengths.

Uploaded by

tj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Graph

Primi*ves

Design and Analysis


of Algorithms I

Dijkstras Algorithm:
The Basics

Single-Source Shortest Paths


Input: directed graph G=(V, E). (m=|E|, n=|V| )
each edge has non negative length le
source vertex s
Output: for each
, compute
L(v) := length of a shortest s-v path in G
Assumption:
1. [for convenience]
2. [important]

Length of path
= sum of edge lengths

Path length = 6

Tim Roughgarden

One of the following is the list of shortest-path distances for the


nodes ,,,, respec*vely. Which is it?
0,1,2,3
0,1,4,7
0,1,4,6
0,1,3,6

Source
vertex

Why Another Shortest-Path Algorithm?


Question: doesnt BFS already compute shortest paths in linear
time?
Answer: yes, IF le = 1 for every edge e.
Question: why not just replace each edge e by directed path of le
unit length edges:
Answer: blows up graph too much
Solution: Dijkstras shortest path algorithm.
Tim Roughgarden

Dijkstras Algorithm

This array
only to help
explanation!

Ini*alize:
X = [s] [ver*ces processed so far]
A[s] = 0 [computed shortest path distances]
B[s] = empty path [computed shortest
paths]
Main Loop
while XV:

-need to grow
x by one node

Main Loop contd:






Already
[call it (v*, w*)] computed in

earlier iteration
add w* to X
set
set

Tim Roughgarden

Example

Dijkstras greedy
score for (v, w):
A[v] + lvw

Tim Roughgarden

Non-Example
Question: why not reduce computing shortest paths with negative
edge lengths to the same problem with non negative lengths? (by
adding large constant to edge lengths)
Problem: doesnt preserve shortest paths !
Also: Dijkstras algorithm incorrect on this graph !
(computes shortest s-t distance to be -2 rather than -4)
Tim Roughgarden

You might also like