Dijkstra算法的核心:选出一个已经求出最短路的点,加上一条边求出另一个点的最短路;d'[v]=min{d[u]+w(u,v)|u的最短距离已求出且边(u,v)存在}  借助堆取出d[u];
http://acm.hdu.edu.cn/showproblem.php?pid=2544

堆+邻接表
花了一上午。。。

#include<iostream>
using namespace std;
#define N 110
#define inf 0x7fffffff
typedef 
struct node{
    
int adj;
    
struct node * next;
    
int w;
}
node,*pnode;
node adjlist[N];
typedef 
struct Heap
{
    
int x;
    
int dis;
}
Heap;
Heap heap[
1000];
bool hash[N];
int len,d[N],n,m;
void insert(Heap in)
{
    
int u=++len;
    
while(u>1&&heap[u>>1].dis>in.dis)
    
{
        heap[u]
=heap[u>>1];
        u
>>=1;
    }

    heap[u]
=in;    
}

Heap pop()
{
    Heap first
=heap[1],last=heap[len--];
    
int u=1,v;
    
while(2*u<=len)
    
{
        v
=u<<1;
        
if(v+1<=len&&heap[v+1].dis<heap[v].dis)
            v
++;
        
if(heap[v].dis<last.dis)
            heap[u]
=heap[v];
        
else
            
break;
        u
=v;        
    }

    heap[u]
=last;
    
return first;
}

void insert_adjlist(int a,int b, int c)
{
    pnode p,q;
    p
=&adjlist[a];    
    
while(p->next!=NULL)
        p
=p->next;
    q
=new node;
    q
->adj=b;
    q
->next=NULL;
    q
->w=c;
    p
->next=q;    
}

int bfs()
{
    Heap min,
in;
    pnode p;
    
in.x=1;
    
in.dis=0;
    d[
1]=0;
    insert(
in);    
    
while(len)
    
{
        min
=pop();
        
if(min.x==n)
            
return min.dis;
        
if(hash[min.x])
            
continue;
        hash[min.x]
=true;        
        p
=adjlist[min.x].next;
        
while(p!=NULL)
        
{
            
if(!hash[p->adj])
            
{
                
in.x=p->adj;
                
in.dis=min.dis+p->w;
                
if(in.dis<d[in.x])
                
{
                    d[
in.x]=in.dis;
                    insert(
in);
                }

            }

            p
=p->next;
        }

    }

    
return -1;
}

int main()
{
    
int i,a,b,c,min;        
    
while(scanf("%d%d",&n,&m),n+m)
    
{
        
for(i=1,len=0;i<=n;i++)
        
{
            adjlist[i].next
=NULL;
            hash[i]
=false;
            d[i]
=inf;
        }

        
        
while(m--)
        
{
            scanf(
"%d%d%d",&a,&b,&c);
            insert_adjlist(a,b,c);
            insert_adjlist(b,a,c);        
        }

        min
=bfs();        
        printf(
"%d\n",min);
    }

}


优先队列+邻接表

#include<iostream>
#include
<queue>
using namespace std;
#define N 110
#define inf 0x7fffffff
typedef 
struct node{
    
int adj;
    
struct node * next;
    
int w;
}
node,*pnode;
node adjlist[N];
typedef 
struct Heap
{
    
bool operator <(Heap T)const
    
{
        
return T.dis<dis;
    }

    
int x;
    
int dis;
}
Heap;
priority_queue
<Heap>Q;
bool hash[N];
int len,d[N],n,m;
void insert_adjlist(int a,int b, int c)
{
    pnode p,q;
    p
=&adjlist[a];    
    
while(p->next!=NULL)
        p
=p->next;
    q
=new node;
    q
->adj=b;
    q
->next=NULL;
    q
->w=c;
    p
->next=q;    
}

int bfs()
{
    Heap min,
in;
    pnode p;
    
while(!Q.empty())
        Q.pop();
    
in.x=1;
    
in.dis=0;
    d[
1]=0;
    Q.push(
in);    
    
while(!Q.empty())
    
{
        min
=Q.top();
        Q.pop();
        
if(min.x==n)
            
return min.dis;
        
if(hash[min.x])
            
continue;
        hash[min.x]
=true;        
        p
=adjlist[min.x].next;
        
while(p!=NULL)
        
{
            
if(!hash[p->adj])
            
{
                
in.x=p->adj;
                
in.dis=min.dis+p->w;
                
if(in.dis<d[in.x])
                
{
                    d[
in.x]=in.dis;
                    Q.push(
in);
                }

            }

            p
=p->next;
        }

    }

    
return -1;
}

int main()
{
    
int i,a,b,c,min;
    
//freopen("123.out","w",stdout);
    while(scanf("%d%d",&n,&m),n+m)
    
{
        
for(i=1,len=0;i<=n;i++)
        
{
            adjlist[i].next
=NULL;
            hash[i]
=false;
            d[i]
=inf;
        }
        
        
while(m--)
        
{
            scanf(
"%d%d%d",&a,&b,&c);
            insert_adjlist(a,b,c);
            insert_adjlist(b,a,c);        
        }

        min
=bfs();        
        printf(
"%d\n",min);
    }

    
return 0;
}



普通的Dijkstra
#include<stdio.h>
#define min(a,b) a>b?b:a
#define inf 0x7FFFFFFF
int map[101][101];
int minload[101];
int visit[101];
int main()
{
    
int start,next,i,j,min,x,y,dis,n,m;
    
while(scanf("%d%d",&n,&m),m||n)
    
{
        
for(i=1;i<=n;i++)
        
{
            minload[i]
=inf;
            visit[i]
=0;
            
for(j=1;j<=n;j++)
                map[i][j]
=inf;
        }

        
while(m--)
        
{
            scanf(
"%d%d%d",&x,&y,&dis);
            map[x][y]
=map[y][x]=dis;
        }

        start
=1;
        visit[
1]=1;
        minload[start]
=0;
        
while(start!=n)
        
{
            min
=inf;
            
for(i=1;i<=n;i++)
            
{
                
if(map[start][i]!=inf)
                    minload[i]
=min(minload[i],minload[start]+map[start][i]);
                
if(!visit[i]&&minload[i]<min)
                
{
                    next
=i;
                    min
=minload[i];
                }

            }
            
            visit[next]
=1;
            start
=next;
        }

        printf(
"%d\n",minload[n]);
    }

}

折腾了半天,感觉如果是比赛的话还是选择最后一种模板,编程复杂度低点(假设题目条件不是那么苛刻
posted on 2009-11-26 14:48 西风萧瑟 阅读(4824) 评论(3)  编辑 收藏 引用 所属分类: 图论

评论:
# re: Dijkstra算法的优化(堆+邻接表,优先队列+邻接表)hdu2544 2009-11-26 21:03 | TimTopCoder
SPFA和Dijkstra相比貌似更强,强烈推荐。  回复  更多评论
  
# re: Dijkstra算法的优化(堆+邻接表,优先队列+邻接表)hdu2544 2009-11-26 21:05 | 西风萧瑟
@TimTopCoder
呵呵,正在学习。。。 谢谢咯  回复  更多评论
  
# re: Dijkstra算法的优化(堆+邻接表,优先队列+邻接表)hdu2544 2013-04-22 20:55 | 苏小柒
hash 的 作用是什么啊,新手刚接触 图论,Heap min ,in in代表的是什么啊  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理