一本色综合网久久,欧美激情精品久久久久,亚洲AV无码久久

數據結構作業之——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 閱讀(3089) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

數據結構作業之——Dijkstra算法鄰接表向量實現（求最短路徑及具體走法）

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

數據結構作業之——Dijkstra算法 鄰接表向量實現（求最短路徑及具體走法）

數據結構作業之——Dijkstra算法鄰接表向量實現（求最短路徑及具體走法）