Scribd
Upload
44 views

Algorithm 2017 Spring: Homework 4 Solutions

This document contains solutions to homework problems about algorithms. It discusses depth-first search and finding negative length cycles. One problem asks to describe a process on a directed graph using vertex a as the source. Another asks when Dijkstra's algorithm will not work and gives the example where it fails to find the shortest path from A to C when a negative edge is present. The document also contains solutions running the DAG-SHORTEST-PATHS algorithm on a sample graph and an algorithm to determine if an undirected graph contains a cycle in O(V) time using depth-first search.

Uploaded by

woogie boogie
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
44 views

Algorithm 2017 Spring: Homework 4 Solutions

This document contains solutions to homework problems about algorithms. It discusses depth-first search and finding negative length cycles. One problem asks to describe a process on a directed graph using vertex a as the source. Another asks when Dijkstra's algorithm will not work and gives the example where it fails to find the shortest path from A to C when a negative edge is present. The document also contains solutions running the DAG-SHORTEST-PATHS algorithm on a sample graph and an algorithm to determine if an undirected graph contains a cycle in O(V) time using depth-first search.

Uploaded by

woogie boogie
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/ 9

Algorithm 2017 Spring

Homework 4 Solutions

指導教授 : 謝孫源 教授
助教 : 許景添 陳琮皓 林玉陞 何岱璇
1. Depth-First-Search algorithm
the timestamp (discovery time & finish time)
2.
After forming the augmented constraint graph and
seeking the shortest path from node 0 to all other
nodes, using an algorithm with negative length
cycle detection, one finds there is a negative length
cycle (2, 3, 5, 4, 2) with length 1 − 7 + 10 − 6 = −2.
Thus the system is infeasible.
3a. (10pts) Describe such a process clearly on the
following di-graph with vertex a as the source.
3b. (10pts) Under what condition Dijkstra’s algorithm
will not work? Given an example to explain your
answer.
在有negative edge 時Dijkstra’s algorithm 可能失效
EX:

用Dijkstra’s algorithm時得到A到C的最短路徑為(A → C)
但實際答案為(A → B → C)
4.Run DAG-SHORTEST-PATHS step by step on the
directed graph of the figure, using vertex s as the
source. (10%)
4. Run DAG-SHORTEST-PATHS step by step on the
directed graph of the figure, using vertex s as the
source. (10%)
5. Give an algorithm that determines whether or not a given
undirected graph G = (V ,E) contains a cycle. Your algorithm
should run in O(V) time, independent of |E|.
◦ An undirected graph is acyclic (i.e., a forest) if and only if a DFS yields no
back edges.
◦ If there is a back edge, there is a cycle.
◦ If there is no back edge, then by Theorem 22.10, there are only tree edges.
◦ Hence, the graph is acyclic.
◦ Thus, we can run DFS: if we find a back edge, there is a cycle.
◦ Time: O(V).(We can simply DFS. If find a back edge, there is a cycle. The
complexity is O(V) instead of O(E + V). Since if there is a back edge, it must
be found before seeing |V | distinct edges. This is because in a acyclic
(undirected ) forest, |E| ≤ |V | - 1, If it has back edge, |E| ≤ |V |)
5. Give an algorithm that determines whether or not a given
undirected graph G = (V ,E) contains a cycle. Your algorithm
should run in O(V) time, independent of |E|.

You might also like