贪婪算法 dijkstra最短路径问题

时间：2009-08-22 来源：ubuntuer

看一个PPT,求一个最短路径问题!!!没想到自己写着写着写成贪婪的了,一只搞不懂分支界定,呵呵!!算法导论上都没讲这个^_^. 好了,这次是抛开书自己拿的思路... 我这里有个小技巧,刚开始的时候路径数组length[]是初始化为一个BIGGEST得数,这个数也用来判断节点是否已经en_queue, de_queue过了，如果进过队列,如果下就更新而已!否则还要en_queue！说的不够清楚,自己看代码。就是避免重复en_queue。 1.首先是广度遍历,把已知节点i可达的其他节点j的length[j]都赋值,en_queue 2.再就是如果有个路径比已知的还小,这个已知的不是BIGGEST 算了写的好麻烦,代码应该很好懂

#include <stdio.h>
#include <stdlib.h>

const int MAX=7;
const int BIGGEST=99999;

typedef struct queue
{
  int front;
  int rear;
  int node[7];
}QUEUE;

void init_queue(QUEUE** Q)
{
  *Q = (QUEUE*)malloc(sizeof(QUEUE));
  (*Q)->front = 0;
  (*Q)->rear = 0;
}

int is_queue_full(QUEUE* Q)
{
  if((Q->rear+1)%MAX == Q->front)
    return 1;

  return 0;
}

int is_queue_empty(QUEUE* Q)
{
  if(Q->rear == Q->front)
    return 1;

  return 0;
}

int en_queue(QUEUE* Q, int node)
{
   if(is_queue_full(Q)==1)
    {
      printf("Sorry the queue is full\n");
      return -1;
    }

   Q->node[Q->rear] = node;
   Q->rear = (Q->rear+1)%MAX;
}

int de_queue(QUEUE* Q)
{
   if(is_queue_empty(Q)==1)
    {
      //printf("Sorry the queue is empty\n");

      return -1;
    }

   int num;
   num = Q->node[Q->front];
   Q->front = (Q->front+1)%MAX;

   return num;
}

void dijkstra(int A[7][7], int length[7], int i)
{
  int j;
  int node_num;
  QUEUE* Q = NULL;
  init_queue(&Q);
  en_queue(Q, i);

  while(1)
  {
   node_num = de_queue(Q);
   if(node_num==-1)
     break;

   for(j=1;j<=MAX;j++)
     if(A[node_num-1][j-1]!=0)
      {
       if(length[j-1]==BIGGEST)
            en_queue(Q, j);

        if(length[node_num-1]+A[node_num-1][j-1]<length[j-1])
           length[j-1] = length[node_num-1]+A[node_num-1][j-1];
      }
  }
}

void print_array(int length[], int n)
{
  int i;
  for(i=0;i<7;i++)
   printf("1->%d:\t%d\n", i+1,length[i]);

  printf("\n");
}

int main(int argc, char *argv[])
{
  int i;
  int A[7][7] = {
       {0,2,0,1,0,0,0},
       {0,0,0,3,10,0,0},
       {4,0,0,0,0,5,0},
       {0,0,2,0,2,8,4},
       {0,0,0,0,0,0,6},
       {0,0,0,0,0,0,0},
       {0,0,0,0,0,1,0},
      };
  int length[7];

  length[0] = 0;
  for(i=1;i<7;i++)
   length[i] = BIGGEST;

  dijkstra(A, length, 1);
  printf("dijkstra is:\n");
  print_array(length, 7);
  system("PAUSE");
  return 0;
}