The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

数据结构作业之——Dijkstra算法 邻接表向量实现(求最短路径及具体走法)

#include<iostream>
#include
<algorithm>
#include
<cstdio>
#include
<stack>
#include
<vector>
using namespace std;

#define  MAX_DOTNUM 1000
#define MAX_INT 999999999

struct node 
{

    
int v;
    
int w;
}
;
vector
<node>myvector[MAX_DOTNUM];
stack
<int>mystack;
int visit[MAX_DOTNUM];
int dis[MAX_DOTNUM];
int pre[MAX_DOTNUM];
int n;

void Dij_plus(int s)
{
    
int i,j;
    memset(visit,
0,sizeof(visit));
    memset(pre,
0,sizeof(pre));
    
for(i=1;i<=n;i++)
    
{
        
if(i==s)
        
{
            dis[i]
=0;
            
continue;
        }

        dis[i]
=MAX_INT;
    }

    
for(i=0;i<myvector[s].size();i++)//vector支持下标运算
    {
        
int v;
        v
=myvector[s][i].v;
        dis[v]
=myvector[s][i].w;
    }

    visit[s]
=1;
    
int temp=MAX_INT;
    
int mark;
    
for(i=1;i<=n;i++)
    
{
        pre[i]
=-1;
    }

    
for(i=0;i<myvector[s].size();i++)
    
{
        
int v=myvector[s][i].v;
        
if(visit[v]!=1)
            pre[v]
=s;
    }

    
for(j=1;j<=n-1;j++)
    
{

        temp
=MAX_INT;
        
for(i=1;i<=n;i++)
        
{
            
if(visit[i]!=1&&dis[i]<temp)
            
{

                temp
=dis[i];
                mark
=i;
            }

        }

    
        visit[mark]
=1;
        
for(i=0;i<myvector[mark].size();i++)
        
{
            
int v=myvector[mark][i].v;
            
if(visit[v]!=1&&myvector[mark][i].w+dis[mark]<dis[v])
            
{
                dis[v]
=myvector[mark][i].w+dis[mark];
                pre[v]
=mark;
            }

        }

    }

}



int main ()
{
    
int s;
    
int i;
    cout
<<"请输入顶点的数目:";
    cin
>>n;
    cout
<<"请输入源点s:";
    cin
>>s;
    cout
<<"请输入边和权,并以0,0,0结束(u,v,w):"<<endl;
    
for(i=1;;i++)
    
{
        
int u,v,w;
        cout
<<"请输入第"<<i<<"条边:";
        cin
>>u>>v>>w;
        
if(u==0&&v==0&&w==0)
            
break;
        node temp;
        temp.v
=v;
        temp.w
=w;
        myvector[u].push_back(temp);
    }

    Dij_plus(s);
    
while(!mystack.empty())
    
{
        mystack.pop();
    }

    
int temp;
    
for(i=1;i<=n;i++)
    
{
        
        
if(i==s)
            
continue;
        
else if(pre[i]==-1)
        
{
            
            printf(
"从%d号点到%d号点没有通路\n",s,i);
            
continue;
        }

        printf(
"从%d号点到%d号点的通路为:",s,i);
        temp
=i;
        
while(temp!=s)
        
{
            
            mystack.push(temp);
            temp
=pre[temp];
        }

        mystack.push(s);
        
while(mystack.size()!=0)
        
{
            printf(
"%d ",mystack.top());
            mystack.pop();
        }

        printf(
"\n");
    }

    system(
"pause");
    
return 0;
}



posted on 2009-04-17 22:33 abilitytao 阅读(2817) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理