有向無環(huán)圖(DAG)單源最短路徑

1签舞、基本算法
我們知道DAG上一定存在拓?fù)渑判颍胰粼谟邢驁DG中從頂點Vi->Vj有一條路徑槽袄,則在拓?fù)渑判蛑许旤cVi一定在頂點Vj之前给僵,而因為在DAG圖中沒有環(huán)毫捣,所以按照DAG圖的拓?fù)渑判蜻M(jìn)行序列最短路徑的更新,一定能求出最短路徑帝际。即使存在權(quán)重為負(fù)的邊,但是它是有向無環(huán)圖,所以它一定不存在權(quán)重為負(fù)的環(huán),所以一定可以求出最短路徑蔓同。
2、基本步驟
處理頂點V時蹲诀,對每條離開的邊<u,v>執(zhí)行松弛運算斑粱。若果<u,v>給出從源點到v的一條最短路徑(經(jīng)過u),則更新到v的最短路徑脯爪。這個過程將檢查圖中每個頂點的所有路徑则北,同時,拓?fù)渑判虼_保按正確的順序處理頂點痕慢。
3尚揣、正確性驗證
如果有向無環(huán)圖包含從結(jié)點u到結(jié)點v的最短路徑,則u在拓?fù)渑判蛑幸欢ㄎ挥趘的前面。我們只需要按照拓?fù)渑判虻拇涡驅(qū)Y(jié)點進(jìn)行一次遍歷處理即可掖举。每次對一個結(jié)點進(jìn)行處理時,我們對該結(jié)點出發(fā)的所有的邊進(jìn)行松弛操作快骗。
4、時間復(fù)雜度:
拓?fù)渑判驗镺( V + E ),松弛操作那部分的代碼的時間復(fù)雜度為O( V + E ),所以時間復(fù)雜度為O( V + E )
偽代碼:
(1)初始化塔次,源點的d值為0方篮,其他的節(jié)點d值為INF。
(2)對DAG進(jìn)行拓?fù)渑判蚶海玫酵負(fù)湫蛄小?br> (3)按照拓?fù)湫蛄斜闅vDAG的點藕溅,對于每個點u,遍歷其所有的出邊<u,v>继榆,如果d[v] > d[u] + length<u,v>巾表,則更新汁掠。

#include <cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXE=1000010;
const int MAXN=100010;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,val,next;
};
Node edge[MAXE];
int head[MAXN];
queue<int> result;
int in[MAXN];
int dis[MAXN];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].val=val;
    head[u]=cnt++;
}
void topoSort(int n)
{
    queue<int> zero;
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0) zero.push(i);
    }
    while(!zero.empty())
    {
        int u=zero.front();
        zero.pop();
        result.push(u);
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            in[v]--;
            if(in[v]==0) zero.push(v);
        }
    }
}
void DAGShortestPath(int st,int n)
{
    topoSort(n);
    memset(dis,INF,sizeof(dis));
    dis[st]=0;
    while(!result.empty())
    {
        int u=result.front();
        result.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==INF) printf("INF\n");
        else printf("%d\n",dis[i]);
    }
}
int main()
{
    int n,m,a,b,val,st;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        scanf("%d",&st);
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&val);
            addEdge(a,b,val);
            in[b]++;
        }
        DAGShortestPath(st,n);
    }
}

Test for Job
題意:
給定一個DAG,求入度為0的點到出度為0的點的最長路徑
題解:

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int MAXE=1000010;
const int MAXN=100010;
const long long INF=-0x7fffffffffffffff;
struct Node
{
    int to,val,next;
};
Node edge[MAXE];
int head[MAXN];
queue<int> result;
int in[MAXN];
int out[MAXN];
long long dis[MAXN];
int weight[MAXN];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].val=val;
    head[u]=cnt++;
}
void topoSort(int n)
{
    queue<int> zero;
    for(int i=0;i<=n;i++)
    {
        if(in[i]==0) zero.push(i);
    }
    while(!zero.empty())
    {
        int u=zero.front();
        zero.pop();
        result.push(u);
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            in[edge[i].to]--;
            if(in[edge[i].to]==0) zero.push(edge[i].to);
        }
    }
}
void DAGShortestPath(int st,int n)
{
    topoSort(n);
    for(int i=0;i<=n;i++) dis[i]=INF;
    dis[st]=0;
    while(!result.empty())
    {
        int u=result.front();
        result.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]<dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
            }
        }
    }
    long long ans=INF;
    for(int i=0;i<=n;i++)
    {
        if(out[i]==0) ans=max(ans,dis[i]);
    }
    printf("%lld\n",ans);
}
int main()
{
    int n,m,a,b,val;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&weight[i]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addEdge(a,b,weight[b]);
            in[b]++;
            out[a]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(in[i]==0)
            {
                addEdge(0,i,weight[i]);
                in[i]++;
                out[0]++;
            }
        }
        DAGShortestPath(0,n);
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市攒发,隨后出現(xiàn)的幾起案子调塌,更是在濱河造成了極大的恐慌,老刑警劉巖惠猿,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異负间,居然都是意外死亡偶妖,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門政溃,熙熙樓的掌柜王于貴愁眉苦臉地迎上來趾访,“玉大人,你說我怎么就攤上這事董虱《笮” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵愤诱,是天一觀的道長云头。 經(jīng)常有香客問我,道長淫半,這世上最難降的妖魔是什么溃槐? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮科吭,結(jié)果婚禮上昏滴,老公的妹妹穿的比我還像新娘。我一直安慰自己对人,他們只是感情好谣殊,可當(dāng)我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著牺弄,像睡著了一般姻几。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上猖闪,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天鲜棠,我揣著相機與錄音,去河邊找鬼培慌。 笑死豁陆,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的吵护。 我是一名探鬼主播盒音,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼表鳍,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了祥诽?” 一聲冷哼從身側(cè)響起譬圣,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎雄坪,沒想到半個月后厘熟,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡维哈,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年绳姨,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片阔挠。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡飘庄,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出购撼,到底是詐尸還是另有隱情跪削,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布迂求,位于F島的核電站碾盐,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏锁摔。R本人自食惡果不足惜廓旬,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望谐腰。 院中可真熱鬧孕豹,春花似錦、人聲如沸十气。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽砸西。三九已至叶眉,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間芹枷,已是汗流浹背衅疙。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留鸳慈,地道東北人饱溢。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像走芋,于是被迫代替她去往敵國和親绩郎。 傳聞我的和親對象是個殘疾皇子潘鲫,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容