Localhost8080

知行合一,自强不息

 

最短路径(单源dijkstra邻接阵)

 

贪心:
code:

//单源最短路径,dijkstra算法,邻接阵形式,复杂度O(n^2)
//求出源s到所有点的最短路经,传入图的顶点数n,(有向)邻接矩阵mat
//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1
//可更改路权类型,但必须非负!
#define MAXN 200
#define inf 1000000000
typedef 
int elem_t;
void dijkstra(int n,elem_t mat[][MAXN],int s,elem_t* min,int* pre)
{
       
int v[MAXN],i,j,k;
       
for (i=0;i<n;i++)
              min[i]
=inf,v[i]=0,pre[i]=-1;
       
for (min[s]=0,j=0;j<n;j++)
      {
              
for (k=-1,i=0;i<n;i++)
                     
if (!v[i]&&(k==-1||min[i]<min[k]))
                            k
=i;
              
for (v[k]=1,i=0;i<n;i++)
                     
if (!v[i]&&min[k]+mat[k][i]<min[i])
                            min[i]
=min[k]+mat[pre[i]=k][i];
       }
}

posted on 2010-10-29 17:35 superKiki 阅读(335) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔档案

文章分类

我的好友

一些常去的网站

搜索

最新评论

阅读排行榜

评论排行榜