LPSA算法

LPSA算法（Longest Path Slower Algorithm）算法是求單源最長路徑的一種算法，是一種高效的最長路算法。

基本介紹

• 中文名：LPSA算法
• 外文名：Longest Path Slower Algorithm
• 外文名解釋：較慢的最長路算法

算法概述

求單源最長路的LPSA算法的全稱是：Longest Path Slower Algorithm，是於1984年發表的。從名字我們就可以看出，這種算法在效率上一定有過人之處。

LPSA的實現和SPFA有異曲同工之妙，關鍵就是把比較時的 > 變成 < 。還有就是因為是求最長路，所以每個點不需要重複入隊，僅需入一次隊。

C++代碼

int lpsa(int s, int t){    memset(dis, 0x3f, sizeof(dis));    memset(vis, 0, sizeof(vis));    queue<int> q;    dis[s] = 0;    vis[s] = 1;    q.push(s);    while(!q.empty()){        int x = q.front();        q.pop();        for(int i = h[x]; i; i = e[i].nxt){            if(dis[e[i].to] < dis[x] + e[i].v){                dis[e[i].to] = dis[x] + e[i].v;                if(!vis[e[i].to]){                    vis[e[i].to] = 1;                    q.push(e[i].to);                }            }        }        vis[x] = 0;    }    return dis[t];}

套用

用於求圖的單源最長路，在最大費用流種套用較廣。