图论之最短路径-------Dijkstra算法

Dijkstra算法（单源最短路径，其边的权值为非负数），其定义为以固定的一个顶点作为源点，求源点到其他顶点的最短路径。

一：

   集合S表示已经加入最短路径的顶点，集合T则表示未加入最短路径的顶点。

二：

  为了求源点v0到各个顶点vi的最段短路径需要设置3个数组，即S[n],path[n],dist[n];

  1.S[n]:S[i]=0时表示vi为加入到集合S中，S[i]=1则表示已经加入到集合S中的顶点。初始时S[v0]=1,其余的均为0.

2.path[n]:path[i]表示v0-->vi这条路径中vi的前一个顶点的序号。

3.dist[n]:dist[i]表示当前找到的v0-->vi的最短路径的长度，初始时dist[i]=Edge[v0][i].Edge[n][n]表示该图的邻接矩阵。

三：

 该算法需要做3个步骤：

1：在diat[n]中查找S[i]!=1,且dist[i]最小的顶点u.

2:将S[u]修改为1，表示u加入到集合S中。

3:修改T中每个顶点的vk的dist及path的值，当u--vk有边且Edge[u][k]<INF（INF为无穷大）且dist[u]+Edge[u][k]<dist[k]时，dist[k]=dist[u]+Edge[u][k],path[k]=u.

四：

 主要代码：

有向图为例：

#include<stdio.h>
#include<string.h>
#define MAXN 20
#define INF 1000000
int n;
int Edge[MAXN][MAXN];
int S[MAXN];
int dist[MAXN];
int path[MAXN];
void Dijkstra(int v0)
{
  int i,j,k;
 for(i=0;i<n;i++)//对s,dist,path进行初始化  关键步骤一
 {
  dist[i]=Edge[v0][i];
  S[i]=0;
  if(i!=v0&&dist[i]<INF)
   path[i]=v0;
  else
   path[i]=-1;
 }
 S[v0]=1;dist[v0]=0;//起初S集合中只有源点  特别注意
 for(i=0;i<n-1;i++)//查找最小路径的顶点u;  关键步骤二
 {
  int min=INF,u=v0;
  for(j=0;j<n;j++)
  {
   if(!S[j]&&dist[j]<min)
   {
    u=j;
    min=dist[j];
   }
  }
  S[u]=1;//表示找到的最小路径的顶点  特别注意呀
  for(k=0;k<n;k++)//对未加入最小路径的顶点的dist和path的值进行修改   关键步骤三
  {
   if(!S[k]&&Edge[u][k]<INF&&dist[u]+Edge[u][k]<dist[k])
   {
    dist[k]=dist[u]+Edge[u][k];
    path[k]=u;
   }
  }
 }
}
int main()
{
 int i,j;
 int u,v,w;
 scanf("%d",&n);
 while(1)
 {
  scanf("%d %d %d",&u,&v,&w);
  if(u==-1&&v==-1&&w==-1)
   break;
  Edge[u][v]=w;
 }
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   if(i==j)
    Edge[i][j]=0;
   else if(Edge[i][j]==0)
    Edge[i][j]=INF;
  }
 }
 Dijkstra(0);
 int shortest[MAXN];//为了记录路径
 for(i=1;i<n;i++)
 {
  printf("%d\t",dist[i]);
  memset(shortest,0,sizeof(shortest));
  int k=0;
  shortest[k]=i;
  while(path[shortest[k]]!=0)
  {
   k++;
   shortest[k]=path[shortest[k-1]];
  }
  k++;
  shortest[k]=0;
  for(j=k;j>0;j--)
   printf("%d->",shortest[j]);
   printf("%d\n",shortest[0]);
 }
 return 0;
}

补充：软件开发 , C语言 ,

上一个：将递增单链表A和递增单链表B合并为递减单链表C
下一个：C与泛型