Dijsktra (directed)－Deja Vu

這個Heap Extractmin的部份寫得很爛

本來有改寫一份

但不知道跑哪去了= =

有機會再修改

不過linked list的部份蠻有創意的

所以記錄下來好了

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <cmath>
#include <ctime>

#define MAX 32767

// structure definition
struct Node {
   long id;
   float weight;
   long value;
}; // end struct Time

void createAdjList( Node **Adj, long numberOfNodes, long degree[] );
//void generateANode( Node &node, long numberOfNodes, long i );
//bool duplicate( Node **Adj, long i, long j );
void printAdjList( long numberOfNodes, long pi[] , long d[]);
void Dijsktra( Node **Adj, long numberOfNodes, long degree[], long d[], long pi[]);

int main()
{

long numberOfNodes;
long time1, time2;

srand( time(0) );

do {
cout << "How many nodes( nodes at least 10 )? ";
cin >> numberOfNodes;
} while( numberOfNodes <= 9);
cout << endl;

time1 = time(0);

long *degree = new long[ numberOfNodes + 1 ];
long *d = new long[ numberOfNodes + 1 ];
// long *color = new long[ numberOfNodes + 1 ];
long *pi = new long[ numberOfNodes + 1 ];

// Node **Adj = new Node*[ numberOfNodes + 1 ];
Node **Adj;
Adj = new Node*[ numberOfNodes + 1 ];

createAdjList( Adj, numberOfNodes, degree );

Dijsktra( Adj, numberOfNodes, degree, d, pi);

printAdjList( numberOfNodes, pi , d );
cout<<endl;
time2 = time(0);
cout << time2 - time1 << " seconds" << endl << endl;

delete [] degree;
for( long i = 1; i <= numberOfNodes; i++ )
delete [] Adj[i];
delete [] Adj;

/*char ch;

cout << "Press any key to continue";
ch = cin.get();
ch = cin.get();*/
system("pause");

return 0;

} // end main

void DFSVISIT(Node **Adj, long numberOfNodes,Node color[],long u,long degree[])
{
color[u].value = 1;
for(long i = 1;i<=degree[u];i++)
{
if( color[Adj[u][i].id].value == 0 )
DFSVISIT(Adj,numberOfNodes,color,Adj[u][i].id,degree);
}
}

void DFS(Node **Adj, long numberOfNodes,Node color[],long degree[])
{

for(long i = 1;i<=numberOfNodes;i++)
color[i].value = 0;

if( color[1].value == 0 )
DFSVISIT(Adj,numberOfNodes,color,1,degree);

}

void createAdjList( Node **Adj, long numberOfNodes, long degree[] )
{
long i,j,k,p,realdegree;
long weightUpperBound = 20;
long numberOfEdges = 0;
// long degreeUpperBound = static_cast<long>(log10(numberOfNodes));
long degreeUpperBound = static_cast<long>(sqrt(numberOfNodes));
long *array = new long[numberOfNodes + 1 ];
Node *color = new Node[numberOfNodes + 1 ];

srand( time(0) );

for( i = 1; i <= numberOfNodes; i++ ) {
  degree[i] = rand() % degreeUpperBound + 1;
  realdegree = degree[1];
  numberOfEdges += degree[i];

}

// cout << "\nThe graph has " << numberOfEdges << " edges.\n";

for(i = 1;i<=numberOfNodes;i++)
{
array[i] = i;
}
Adj[1] = new Node[numberOfNodes + 1];

cout<<"Tree: "<<endl;
for( i = 1; i <= numberOfNodes; i++ )
{

if( i>1 )
Adj[i] = new Node[ degree[i] + 1 ];

  p = numberOfNodes;

   //cout<<i<<"-> ";
   for( j = 1; j <= degree[i] ; j++)
   {

    k = rand() % p + 1;

    while(i==k)
    {
     k = rand() % p + 1;
    }

Adj[i][j].id = array[k];

    if( k!=p )
    {
     if( p==i )
     {
      array[k] = array[p-1];
      p--;
     }
     else
     array[k] = array[p];
    }
    p--;

Adj[i][j].weight = rand() % weightUpperBound + 1; //放入weight arrary亂數值且不超過weightUpperBound

// cout<<" ("<<Adj[i][j].id<<" , "<<Adj[i][j].weight<<")";

}

   //cout<<endl;
   for(long k = 1;k<=numberOfNodes;k++)
   {
    array[k] = k;
   }

}

DFS(Adj,numberOfNodes,color,degree);

for(long s = 1;s<=numberOfNodes;s++)
{
  if( color[s].value == 0 )
  {
   realdegree++;
   Adj[1][realdegree].id = s;
   Adj[1][realdegree].weight = rand() % weightUpperBound + 1;
  }
}
degree[1] = realdegree;

for( i = 1; i <= numberOfNodes; i++ )
{
  cout<<i<<"-> ";
  for(j = 1;j<=degree[i];j++)
  {
   cout<<" ("<<Adj[i][j].id<<" , "<<Adj[i][j].weight<<")";
  }
  cout<<endl;
}

cout<<endl;

}

void MinHeapify( long Q[], long i, long numberOfNodes,long d[] )
{
long l,r,mini,buffer;
l = 2*i;
r = (2*i)+1;

if( l<=numberOfNodes && Q[l]<Q[i] )
  mini = l;
else
  mini = i;
if( r<=numberOfNodes && Q[r]<Q[mini] )
  mini = r;

if( mini != i )
{
  buffer = Q[i];
  Q[i] = Q[mini];
  Q[mini] = buffer;

MinHeapify(Q,mini,numberOfNodes,d);
}

}

long HeapExtractMin( long Q[], long &count,long d[] ,long numberOfNodes)
{
long min;
min = Q[1];
Q[1] = Q[count];
count--;
MinHeapify(Q,1,numberOfNodes,d);
return min;
}

void HeapDecreaseKey( long Q[], long i, long key,long d[])
{
long buf,par;
par = i/2;

Q[i] = key;
while( i > 1 && Q[par] > Q[i] )
{
  buf = Q[i];
  Q[i] = Q[par];
  Q[par] = buf;
  i = par;
  par = i/2;
}
}

void MinHeapInsert( long Q[],long key,long numberOfNodes,long d[] )
{
numberOfNodes++;
Q[numberOfNodes] = -10000;
HeapDecreaseKey(Q,numberOfNodes,key,d);
}

void Dijsktra( Node **Adj, long numberOfNodes, long degree[], long d[], long pi[])
{
long *Q = new long[numberOfNodes + 1 ];
long *array = new long[numberOfNodes + 1 ];
long u,count,tail,k,buf;
long s = 1;
count = numberOfNodes;
tail = numberOfNodes;

for( long i = 1; i <= numberOfNodes; i++ )
{
  d[i] = 10000;
  pi[i] = NULL;
  MinHeapInsert(Q,d[i],i,d);
  array[i] = i;

}

d[s] = 0;

HeapDecreaseKey(Q,s,d[s],d);

while( count != 0 )
{
  u = HeapExtractMin( Q,count,d,numberOfNodes);
  k = 1;

  while( tail != 0 && k<=tail )
  {
   if( d[array[k]] == u )
   {
    for( long j = 1;j<=degree[array[k]];j++ )
    {
     if( d[Adj[array[k]][j].id] > d[array[k]]+Adj[array[k]][j].weight )
     {
      d[Adj[array[k]][j].id] = d[array[k]]+Adj[array[k]][j].weight;
      pi[Adj[array[k]][j].id] = array[k];
      HeapDecreaseKey(Q,Adj[array[k]][j].id,d[Adj[array[k]][j].id],d); //////////
     }
    }
    buf = array[k];
    array[k] = array[tail];
    array[tail] = buf;
    tail--;
    break;
   }
   k++;
  }


}
}

void printAdjList( long numberOfNodes, long pi[] , long d[] )
{
cout<<"Tree edges: "<<endl;
for(long i = 1;i<=numberOfNodes;i++ )
{
  cout<<"("<<pi[i]<<" , "<<i<<")"<<endl;
}
cout<<endl;
for(long j = 1;j<=numberOfNodes;j++ )
{
  if( d[j] == 10000 )
   cout<<"d["<<j<<"] = 無限大"<<endl;
  else
   cout<<"d["<<j<<"] = "<<d[j]<<endl;
}
}