Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。问题描述
在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径） 迪杰斯特拉(Dijkstra)算法思想 按路径长度递增次序产生最短路径算法： 把V分成两组： （1）S：已求出最短路径的顶点的集合 （2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 （反证法可证） 求最短路径步骤 算法步骤如下： 1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 若不存在<V0,Vi>，d(V0,Vi)为∝ 2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S 3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的 距离值比不加W的路径要短，则修改此距离值 重复上述步骤2、3，直到S中包含所有顶点，即S=T为止 代码： 源地址：
www.cnblogs.com/newwy /*********************************
* 最短路径---Dijkstra算法实现
* HDU：2544
* BLOG:www.cnblogs.com/newwy
* AUTHOR:Wang Yong
**********************************/
#include <iostream>
#define MAX 100
#define INF 1000000000
using namespace std;
int dijkstra (int mat[][MAX],int n, int s,int f)
{
int dis[MAX];
int mark[MAX];//记录被选中的结点
int i,j,k = 0;
for(i = 0 ; i < n ; i++)//初始化所有结点，每个结点都没有被选中
mark[i] = 0;
for(i = 0 ; i < n ; i++)//将每个结点到start结点weight记录为当前distance
{
dis[i] = mat[s][i];
//path[i] = s;
}
mark[s] = 1;//start结点被选中
//path[s] = 0;
dis[s] = 0;//将start结点的的距离设置为0
int min ;//设置最短的距离。
for(i = 1 ; i < n; i++)
{
min = INF;
for(j = 0 ; j < n;j++)
{
if(mark[j] == 0 && dis[j] < min)//未被选中的结点中，距离最短的被选中
{
min = dis[j] ;
k = j;
}
}
mark[k] = 1;//标记为被选中
for(j = 0 ; j < n ; j++)
{
if( mark[j] == 0 && (dis[j] > (dis[k] + mat[k][j])))//修改剩余结点的最短距离
{
dis[j] = dis[k] + mat[k][j];
}
}
}
return dis[f];
}
int mat[MAX][MAX];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m))
{
int a,b,dis;
if(n == 0 || m == 0)
break;
int i,j;
for(i = 0 ; i < n;i++)
for(j = 0 ; j < n; j++)
mat[i][j] = INF;
for(i = 0 ; i < m ;i++)
{
scanf("%d %d %d",&a,&b,&dis);
--a,--b;
if(dis < mat[a][b] || dis < mat[b][a])
mat[a][b] = mat[b][a] = dis;
}
int ans = dijkstra(mat,n,0,n-1);
printf("%d\n",ans);
}
}
可用 优先队列优化
其他解释：
http://blog.csdn.net/jiahui524/article/details/6636913
posted on 2012-06-16 03:53
luis 阅读(534)
评论(0) 编辑 收藏 引用 所属分类:
图论*矩阵