频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
单源最短路模板
2013-02-02 10:29:20           
收藏   我要投稿

 

一:SPFA

#define INF 1000000000  

#define MAXN 50010  //点个数  

#define MAXM 6000000 //边条数  

int dis[MAXN];//结果  

struct Node{  

    int v, next;  

    int  c;  

}E[MAXM];  

int head[MAXN];  

int NE;  

void init(int n)  

{  

    for (int i = 0; i <= n; i ++)  

    {  

        head[i] = -1;  

        dis[i] = INF;  

    }  

    NE = 0;   

}  

  

void insert(int x, int y, int c)  

{  

    E[NE].v = y;  

    E[NE].c = c;  

    E[NE].next = head[x];  

    head[x] = NE ++;  

}  

  

bool spfa(int s, int n)//s为起点  

{  

    int p,i;  

    queue<int>q;  

    while(!q.empty())  

        q.pop();  

  

    bool hash[MAXN];  

    int count[MAXN];  

    memset (count, 0, sizeof(int) * (n + 2));  

    memset(hash,0,sizeof(bool) * ( n + 2)) ;  

  

    hash[s] = 1;  

      

    dis[s] = 0;  

    q.push(s);  

    count [s] = 1;  

    while(!q.empty())  

    {  

        p = q.front();  

        q.pop();  

        if(count[p] > n)  

            return false; //负环  

        hash[p] = 0;  

        for(i = head[p]; i != -1; i = E[i].next)  

        {  

            int v = E[i].v;  

            int cc = E[i].c;  

            if(dis[p] + cc < dis[v] || dis[v] == INF)    

//v - u <= k时候是这样的,如果v - u >= k 改符号  

            {  

                dis[v] = dis[p] + cc;  

                if(hash[v] == 0)  

                {  

                    count[v] ++;  

                    hash[v] = 1;  

                    q.push(v);  

                }  

            }  

        }  

    }  

    return 1;  

}  

 

二:dijstra

 

const int N = 1001; //点  

using namespace std;  

struct node  

{  

    int l,dir;  

}w;//边  

struct In  

{  

    int idx;  

    int l;  

    bool friend operator<(const In &a, const In &b)  

    {  

        return a.l > b.l;  

    }  

}ww,zz;//bfs  

vector<node>mmap[N];  

priority_queue<In>q;  

int dis[N];  

int start, end; //start 起点, end 终点  

int nodenum;//点数 = end  

int n, m;  

int base;  

void init()  

{  

    while (!q.empty())  

        q.pop();  

    int i;  

    for (i = 0; i <= nodenum; i++)  

    {  

        dis[i] = -1;  

        mmap[i].clear();  

    }  

    return;  

}  

  

inline void creat(int s, int e, int value)   

{  

    w.l = value;  

    w.dir = e;  

    mmap[s].push_back(w);  

    return;  

}  

void dij()  

{  

    int i, j;  

    ww.idx = start;  

    ww.l = 0;  

    int size = 0;  

    node now;  

    q.push(ww);  

    while (!q.empty())  

    {  

        ww = q.top();  

        q.pop();  

          

        if (dis[ww.idx] != -1)  

            continue;  

        dis[ww.idx] = ww.l;  

        if(ww.idx == end)  

            return;  www.2cto.com

        size = mmap[ww.idx].size();  

        for (i = 0;i < size; i++)  

        {  

            now = mmap[ww.idx][i];  

            zz.idx = now.dir;  

            zz.l = ww.l + now.l;  

            if(dis[zz.idx] == -1)  

            {  

                q.push(zz);  

            }  

        }  

    }  

    return;  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 模板 单源
上一篇:OpenStack的G版Keystone对象模型
下一篇:网络最大流(SAP)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站