The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

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

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 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算法鄰接表向量實現（求最短路徑及具體走法）