Dijkstra 算法去单源最短路径
//Dijkstra算法只能处理正边权问题#include <iostream>#include<cstdio>#include<cstring>#define MAX 100#define VALUE 0xffffffusing namespace std;int g[MAX][MAX];int d[MAX];//某一个点到所有点的最短距离bool used[MAX];//已经被使用的标记int v,e;void createGraph(){ int i; int start,end,weight; memset(g,0,sizeof(g)); scanf("%d%d",&v,&e); for(i=0;i<e;i++) { scanf("%d%d%d",&start,&end,&weight); g[start][end]=weight; g[end][start]=weight; }}/*从某一个点到任意一点的最短距离*/void Dijkstra(int s){ for(int i=1;i<=v;i++) { d[i]=VALUE; used[i]=false; } d[s]=0; while(true) { int t=-1;int u; //从尚未使用的顶点中找出距离最短的 for(u=1;u<=v;u++) { //遍历每个点，如果该点没被使用过，并且（v==-1 或者s到u的距离小于s到t的距离（找出与s相连的权值最小的边对应的点t）） if(!used[u] && (t==-1 || d[u]<d[t])) t=u; } if(t==-1) break; used[t]=true; for(u=1;u<=v;u++) {//如果s到u的最短距离大于s到t的最短距离加上t到u的权值（t到u有边），那么更新s点到任意一点的距离 if(d[u]>d[t]+g[t][u] && g[t][u]!=0)d[u]=d[t]+g[t][u]; } } for(int u=1;u<=v;u++) { printf("%d ",d[u]); }}int main(){ createGraph(); Dijkstra(1); return 0;}/*5 81 2 22 3 33 4 24 5 31 3 51 4 12 4 72 5 3*/