最短路径，其实就是求我们日常生活中，从某点到达某点的最短路径，Dijkstra用了一种变通的方式，它是求出从源点到达所有点的最短路径长度。  

分析:

这个算法采用的是贪心思想，而贪心算法能否达到最后，有两个必要不充分条件

1.必须要有最优子结构 2.必须具备贪心选择属性

1.最优子结构:

我们设d(i,j)表示从，结点Vi到Vj的最短路径值，则d（i，j） = d（i，k） + d（k，j）(假设k是最短路上经过的点)。这就是最短路的问题的最优子·结构，因为原问题的最优解，取决于两个不想交子集的最优解。

2.贪心选择属性

我们假设Set（i，j）表示从{d[i],....d[j]}的集合，而d[k]又表示为从源点到结点k的最短距离，则当要要拓展即d[j + 1]时，因该把此时离源点距离最近的选入，这样Set的补集，就有减少了一个结点，我们接下去要解决的就只是有少了一个结点的子问题，如果把这个补集的元素到源点的距离按照从小到大排序，那么此时要选的就是最小的。这个就是贪心选择属性，它每一次都选则最小的，接着继续解决下一个子问题（解着下次选择）。又因为，其实选的时候，我们只需要考虑于已经算出的点的最短距离有邻接的点，所以我们需要更新所有邻接点，而其它的点此时的d值为多少，并无关系。所以我们初始话时可以把d都设置为INF,然后记录下相邻节点间的权值就够，也就是说这个贪心选择，能保证每次选入的点，到达源点的距离是最短的。

代码如下:

#include 
    
     #include 
     
      #define INF 1 << 30#define MAXN 1000int d[MAXN + 1];int fa[MAXN + 1];int vis[MAXN + 1];int G[MAXN + 1][MAXN + 1];//这里可以换为Vector数据结构，降低空间复杂度 int n,m;int main(){		while(scanf("%d%d",&n,&m) != EOF){		for(int i = 1; i <= MAXN ; i++){//初始化图，为无边图 			for(int j = 1; j <= MAXN; j++){				G[i][j] = INF;			}		}		for(int i = 1; i <=m; i++){//建立图 			int u,v,w;			scanf("%d%d%d",&u,&v,&w);			G[u][v] = w;		}		d[1] = 0;//源点到自身，距离为0，设源点为V1. 		fa[1] = 1; 		for(int i = 2; i <= n; i++){			d[i] = INF;			fa[i] = 0;		} 		memset(vis,0,sizeof(vis));		for(int i = 1; i <= n; i++){			int min = INF,x;			for(int y = 1; y <= n; y++){				if(!vis[y] && d[y] <= min){					min = d[x = y]; 				}			}			vis[x] = 1;//加入集合Set 			for(int y = 1; y <=n; y++){//跟新x的邻接点，只有边不为INF才不会改变，边权值为INF视为不是邻接点，所以并不会改变 				if(d[y] > d[x] + G[x][y]){					d[y] = d[x] + G[x][y];					fa[y] = x;				}			} 		}		for(int i = 1; i <= n; i++)			printf("%d\n",d[i]);	} 	return 0;}
     
    

这段代码如果要算无向图，在建立图时，只要稍微修改下而已。

2013 04 26

By ACReaper