首页 > 代码库 > Dijkstra(单源最短路算法)

Dijkstra(单源最短路算法)

typedef struct graph{

  int val;
  int weight;
}
graph;


graph g[1005][1005],dist[1005];
int visit[1005];

void dijkstra(int start,int n)

{
  int min,u;
  for(int i=1;i<=n;i++)

  {
    dist[i].val = MAXVAL;
    visit[i]=0;
  }
  for(int i=1;i<=n;i++)

  {
    if(g[start][i].val < MAXVAL)

    {
      dist[i].val = g[start][i].val;
      dist[i].weight = g[start][i].weight;
    }
  }
  visit[start] = 1;
  dist[start].val = 0;

  for(int i=1;i<=n;i++)

  {
    min = MAXVAL;
    u = 0;
    for(int k=1;k<=n;k++)    //找出每一轮最短路径的顶点

    { 
      if(visit[k]==0 && dist[k].val < min)

      {
        min = dist[k].val;
        u = k;
      }
    }
    visit[u] = 1;
    for(int j=1;j<=n;j++)    //更新最短路径

    { 
      if(visit[j]==0 && dist[j].val > (dist[u].val + g[u][j].val))

      {
        dist[j].val = dist[u].val + g[u][j].val;
        dist[j].weight = dist[u].weight + g[u][j].weight;
      }

      else if(visit[j]==0 && dist[j].val == (dist[u].val + g[u][j].val))

      {
        if(dist[j].weight > (dist[u].weight + g[u][j].weight))

        {
          dist[j].weight = dist[u].weight + g[u][j].weight;
        }
      }
    }
  }
}

Dijkstra(单源最短路算法)