This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
df.c Actully Introduces A Way To Think Of Algorithm
- From: lin zuojian <manjian2006 at gmail dot com>
- To: gcc at gcc dot gnu dot org
- Date: Thu, 16 Oct 2014 14:13:14 +0800
- Subject: df.c Actully Introduces A Way To Think Of Algorithm
- Authentication-results: sourceware.org; auth=none
Hi,
I don't know if this is mentioned before, df.c is introducing a very
good way to think of algorithms. It brings two effective orders to
handle many problems: DF_FORWARD and DF_BACKWARD. They means two
fact respectively: a subproblem will not be accessed until all
its parents get accessed; And a problem will not be accessed until
all its subproblems get accessed.
The single source shortest path will have a O(n) solution instead of
O(n + log(n)) if using DF_FORWARD. Defining
df_confluence_function_n like following:
{
if(e->wight + e->src->total_wight < e.dest->total_wight)
{
e->dest.total_wight = e->wight + e->src->total_wight;
e->dest.parent = e->src;
}
}
I think it's really O(n) for a dfs right?
That's what I want to proposed.
--
Lin Zuojian