注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

最短路  

2009-08-10 08:43:29|  分类: 资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

dijkstra O(n^2)  确切来说 是O(N^2+N^2) 用堆最大优化后O((V+E)logn)
大约 代码
int dij()
{
    int i,j,k;
    for(i=0;i<=N;i++) {dist[i]=c[0][i];s[i]=0;}
    s[0]=1;use[0]=1;
   
    for(i=1;i<=N;i++)
    {
        tmin=inf;
       //1.此处 可以用堆优化就是heap+dijkstra 建堆,先将原点的DIS值,加入堆
       //2.每次取最小值,再将更新时,所有更新的结点加入到堆
        for(j=1;j<=N;j++)//寻找当前未被纳入符合最短距离的结点

        {
            if(!s[j]&&use[j]&&tmin>dist[j])
            {
                k=j;
                tmin=dist[j];
            }
        }
        s[k]=1;//将k号结点纳入最短路
        for(j=1;j<=N;j++)//对与k有关的结点进行更新 使用邻接表 优化 更快
        {
            if(!s[j]&&use[j]&&dist[k]<inf&&c[k][j]<inf&&dist[j]>dist[k]+c[k][j])
                dist[j]=dist[k]+c[k][j];
        }
    }
    return dist[1];
}
附上 找来的 这么废 写得~~ 修改之
#include<iostream>
using namespace std;
//堆
void insert()
int getit()
struct edge{
       int j,w;
       edge *next;
}*g[maxn],*pool;
       graph(int node_num,int edge_num):node_num(node_num){
         memset(g,0,sizeof(g));
         pool=new edge[2*edge_num];
         allop_pt=0;
       }
       ~graph(){
            delete[] pool;   
    }
    inline edge* new_edge(int j,int w,edge* next){
       pool[allop_pt].j=j;
       pool[allop_pt].w=w;
       pool[allop_pt].next=next;
       return &pool[allop_pt++];
       }
    inline void add_edge(int i,int j,int w){
         g[i]=new_edge(j,w,g[i]);
         g[j]=new_edge(i,w,g[j]);
       }   
};
void dijkstra(graph& g,int source, int dis[]){
  bool known[maxn]={0};
  for(int i=0;i<g.node_num;i++)dis[i]=INF;
  dis[source]=0;
  MinBinaryHeap heap(g.node_num);
  heap.build_heap(dis,g.node_num);
  for(int k=0;k<g.node_num;k++){
      pair<int,int> tem=heap.pop();  
      int i=tem.first;
      known[i]=true;
      for(graph::edge* e=g.g[i];e;e=e->next){
      if(!known[e->j] && dis[e->j] > dis[i]+e->w){ 
         dis[e->j]=dis[i]+e->w;
         heap.decrease_to(e->j,dis[e->j]);
              }
   }
     }
}


bellman-ford 复杂度O(NE)
用struct U,V,W表实现 适用于找负权环(即最短路 不存在)
void bellford()
{
int i,j,k; bool p=0; int f[100];
for(i=1;i<=n;i++) f[i]=MAXINT;
f[s]=0;
for(k=0;k<n;k++)//N个结点,进行N-1次松弛
{
   p=1;
   for(i=1;i<=n;i++)
   for(j=0;j<e[i].size();j++)
       if(f[i]+len[i][j]<f[e[i][j]])
    {
    f[e[i][j]]=f[i]+len[i][j];
    p=0;
    }
   if(p) break;
}
if(f[t]==MAXINT||!p) cout<<"no way!"<<endl;//判断找负环
else cout<<f[t]<<endl;
}

 

SPFA
使用邻接表实现
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=100000,INF=0x11111111;;
struct graph{
    int node_num,allop_pt;
    struct edge{
        int j,w;
        edge *next;
       }*g[maxn],*pool;
       graph(int node_num,int edge_num):node_num(node_num){
         memset(g,0,sizeof(g));
         pool=new edge[2*edge_num];
         allop_pt=0;
       }
       ~graph(){
            delete[] pool;   
    }
    inline edge* new_edge(int j,int w,edge* next){
       pool[allop_pt].j=j;
       pool[allop_pt].w=w;
       pool[allop_pt].next=next;
       return &pool[allop_pt++];
       }
    inline void add_edge(int i,int j,int w){
         g[i]=new_edge(j,w,g[i]);
         g[j]=new_edge(i,w,g[j]);
       }   
};
int Q[65536];
void SPFA(graph &g,int source,int dis[]){
    int qsize=65535,f=0,b=0;
    bool in[maxn]={0};
    for(int i=0;i<g.node_num;i++)dis[i]=INF;
    dis[source]=0;
    Q[f++]=source;f&=qsize;
    in[source]=true;
    while(f!=b){
         int i=Q[b++];b&=qsize;
   in[i]=false;
   for(graph::edge *e=g.g[i];e;e=e->next){
           if(dis[e->j] > dis[i]+e->w){ 
          dis[e->j]=dis[i]+e->w; 
          if(!in[e->j]){
         Q[f++]=e->j;f&=qsize;
      in[e->j]=true;     
            }
           } 
   }     
       } 
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
       int dis[maxn];
       int n,m,a,b,c;
       scanf("%d%d",&n,&m);
       graph G(n,m);
       while(m--){
         scanf("%d%d%d",&a,&b,&c);
         G.add_edge(a,b,c);
       }
       SPFA(G,0,dis);
       for(int i=0;i<n;i++)printf("%d\n",dis[i]);
}

 

floyd O(n^3)
Floyd算法适用于APSP(All Pairs Shortest Paths),是一种动态规划算法,稠密图效果最佳,边权可正可负。
此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法。
void floyed()
{
__int64 f[100][100]; int i,j,k;

for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
     if(c[i][j]>0||i==j) f[i][j]=c[i][j];
         else f[i][j]=MAXINT;

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
   if(f[i][k]+f[k][j]<f[i][j])
       f[i][j]=f[i][k]+f[k][j];
if(f[s][t]==(__int64)MAXINT) printf("no way!\n");
    else printf("%I64d\n",f[s][t]);
}

 

  评论这张
 
阅读(151)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018