dijkstra算法演示
浏览数：266 /
时间：2015年06月08日
dijkstra算法演示精髓
#include <iostream> #include <fstream> #include <cstring> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <cmath> using namespace std; #define loop(i,n) for(int i=0;i<(n);i++) #define loop2(i,n) for(int i=1;i<=(n);i++) const int maxn=10; int inf=99999999; int e[maxn][maxn],dis[maxn],book[maxn]; int n,m; void dijkstra(void) { //找到离1号顶点最近的点 int u,v; int xmin; loop2(i,n-1) { xmin=inf; loop2(j,n) { if(book[j]==0 && dis[j]<xmin) { xmin=dis[j]; u=j; } } book[u]=1; loop2(v,n) //松驰 { if(e[u][v]<inf) if(dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } } void test() { freopen("dijkstra.in","r",stdin); //freopen("dijkstra.out","w",stdout); cin>>n>>m; cout<<n<<" "<<m<<endl; loop2(i,n) loop2(j,m) if(i==j)e[i][j]=0; else e[i][j]=inf; int t1,t2,t3; loop2(i,m) { cin>>t1>>t2>>t3; e[t1][t2]=t3; } loop2(i,n) dis[i]=e[1][i]; book[1]=1; dijkstra(); loop2(i,n) cout<<dis[i]<<" "; cout<<endl; } int main () { test(); return 0; }
test data:
6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
