[go: up one dir, main page]
Scribd
Upload
5 views22 pages

Session23 Graphs II

Uploaded by

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

Session23 Graphs II

Uploaded by

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

GRAPHS CONT.

SHORTEST PATH ON WEIGHTED


GRAPH
Edsger Wybe Dijkstra:
https://en.wikipedia.org/wiki/Edsger_W._Dijk
stra
• Dijkstra’s algorithm finds the shortest path from vertex A to
vertex B, in a weighted graph.
• But…
GRAPHS WITH NEGATIVE WEIGHTS
GRAPHS WITH NEGATIVE WEIGHTS

• Example: Trading a book for a set of drums

Wrong!
GRAPHS WITH NEGATIVE WEIGHTS

• Shortest Path Search can be accomplished using Bellman-


Ford algorithm:
Initialize the table of costs to reach each vertex.

For each Vertex in the graph:


- For each edge in the graph:
- Update the cost to reach vertex v from
vertex u, in the table of costs.

Run an extra check to verify the graph is stable.


This is, the graph would not render different results
if we try to update the costs to reach each vertex.
CAVEAT IN BELLMAN-FORD

• It does not work if the graph has negative cycles:

The cost to reach each node of


the cycle is
CYCLES

Strongly Connected
Components:
Maximal set of vertices such that
for every pair of vertices u and v,
both are reachable from each
other.
CYCLE DETECTION: DEPTH-FIRST
SEARCH TO THE RESCUE

• Traverse edges as deep as possible before continuing with


other paths:

D
C
A
E

B D
https://visualgo.net/en/
dfsbfs
So….?
𝑂 (𝑛+ 𝑚)
Remember: n is the number of vertices (|V|) and m the number of
edges (|E|)
We must traverse all vertices, and all edges present in the graph.
CYCLE DETECTION

• We need two states for each vertex:


• Visiting (grey): while we are walking through any o its descendants
• Visited (black): When we leave any path where that vertex is present
TOPOLOGICAL SORT

• A graph with no cycles is called Acyclic Graph


• A directed graph with no cycles is a DAG (Directed Acyclic
Graph)
• DAGs can have one or many topological orderings
TOPOLOGICAL SORT
TOPOLOGICAL SORT

• Just as other applications, like shortest path, only work with


BFS, Topological Sort can only be accomplished using DFS.
https://www.cs.usfca.edu/~galles/visualization/Top
oSortDFS.html
And….?
𝑂 (𝑛+ 𝑚)
Remember: n is the number of vertices (|V|) and m the number of
edges (|E|)
We must traverse all vertices, and all edges present in the graph.
EXERCISE

• Given the graph below, what are the possible topological


orderings from node p to node v?

• pov
• poryv
• posryv
• psryv

You might also like