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 阅读(2723) 评论(0)  编辑 收藏 引用


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