Dijistra最短路径 邻接巨阵结构 c++.rar_Dijistra_最短路_最短路径_最短路径c-c

中国运筹学会 ? 游客: 注册 | 登录 | 会员 | 帮助 返回 中国运筹学会 中国运筹学会 ? 运筹算法与软件 ? Dijistra最短路径 邻接巨阵结构 c++ （n^2）zz 作者: 标题: Dijistra最短路径 邻接巨阵结构 c++ （n^2）zz 上一主题 | 下一主题 Aciclovir Administrator 积分 4747 发贴 532 注册 2004-1-9 状态 离线 Dijistra最短路径 邻接巨阵结构 c++ （n^2）zz Dijistra最短路径 邻接巨阵结构 c++ （n^2） #include <iostream> #include <fstream> #include <iomanip> #include <cmath> #include <algorithm> #include <deque> using namespace std; ifstream fin("Dijistra.in"); #define NN 10000 // Dijistra求有向图（邻接表存储结构 v[n]是一个 队列)中 // 点s到其于顶点的最短路。 // 数组d[n]存储最终结果。 flag[n]是标志数组。 int n,m,s; // n为顶点数，m为边数，s为起点。 int flag[NN],d[NN]; // 一律以0为起始单元。 typedef struct Cseg{ int y,dist; }Cseg; Cseg c1; deque <Cseg> v[NN]; void dijistra(int s); int getmin(); void in(); int main() { in(); dijistra(s); getchar(); fin.close(); return 0; } void dijistra(int s) { int i,j,k; memset(flag,0,sizeof(flag)); memset(d,0,sizeof(d)); for (i=0;i<v[s].size();i++) d[v[s].y]=v[s].dist; d[s]=0; flag[s]=1; for (;;){ k=getmin(); flag[k]=1; if (k==-1) break; for (i=0;i<v[k].size();i++){ int y; y=v[k].y; if (d[y]==0 || d[y]>d[k]+v[k].dist) d[y]=d[k]+v[k].dist; } } //out cout<<"s= "<<s<<endl; for (i=0;i<n;i++) cout<<"d [ "<<i<<" ]= "<<d<<endl; return; } int getmin() { int i,rec=-1; for (i=0;i<n;i++) if (!flag) if (d!=0) if (rec==-1) rec=i; else if (d[rec]>d) rec=i; return rec; } void in() { int i,x,y,dist; fin>>n>>m; // memset(map,0,sizeof(map)); for (i=0;i<n;i++) v.clear(); for (i=0;i<m;i++){ fin>>x>>y>>dist; c1.y=y;c1.dist=dist; v[x].push_back(c1); } fin>>s; return; } -- 2004-4-20 18:45 可打印版本 | 推荐给朋友 | 订阅主题 | 收藏主题 论坛跳转: 日常事务 > 中国运筹学会公告板 学术天地 > 运筹算法与软件 > 学术会议发布 > 新书推荐 > 书评天地 > 不确定理论&不确定规划 不确定系统分会 > 加盟不确定系统分会 > 不确定系统分会会员录 > 学术讲座 > 学术沙龙 > 讲习班 友情链接 > UTLab (清华大学不确定理论实验室) > UTLab Seminar < 联系我们 - 中国运筹学会 > Powered by Discuz! 2.0 COML ? 2002, Crossday, Bokavan Corp. Processed in 0.075725 second(s), 6 queries