The Fourth Dimension Space

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

数据结构作业之——Dijkstra算法邻接矩阵实现（求最短路径及具体走法）

 

//Get Guidence By Mr Zhong Hong
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
#define  MAX_DOTMUN 1000
#define MAX_INT 999999999

int visit[MAX_DOTMUN];
int dis[MAX_DOTMUN];
int mymap[MAX_DOTMUN][MAX_DOTMUN];
int pre[MAX_DOTMUN];
int n;
stack<int>mystack;




void Dij_plus(int s)
{
    memset(visit,0,sizeof(visit));
    memset(pre,0,sizeof(pre));
    int i,j;
    for(i=1;i<=n;i++)
    {
        dis[i]=mymap[s][i];
    }
    visit[s]=1;
    int temp=MAX_INT;
    int mark;
    for(i=1;i<=n;i++)
        pre[i]=-1;
    for(i=1;i<=n;i++)
    {
        
        if(visit[i]!=1&&mymap[s][i]!=MAX_INT)
            pre[i]=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=1;i<=n;i++)
        {

            if(visit[i]!=1&&mymap[mark][i]+dis[mark]<dis[i])
            {
                dis[i]=mymap[mark][i]+dis[mark];
                pre[i]=mark;
            }

        }
    }
}


int main ()
{
    int s;
    int i,j;
    cout<<"请输入顶点的数目:";
    cin>>n;
    cout<<"请输入源点s:";
    cin>>s;
    for(i=1;i<=n;i++)
    {

        for(j=1;j<=n;j++)
        {
            if(i==j)
                mymap[i][j]=0;
            else
                mymap[i][j]=MAX_INT;
        }
    }
    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;
        mymap[u][v]=w;
    }
    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-16 13:45 abilitytao 阅读(3416) 评论(0)  编辑 收藏 引用


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