Timmy's Blog

Test9.cpp
[codes=c]
#include<iostream.h>
#include<stdlib.h>
#include<strstrea.h>
typedef int VertexType;
typedef int WeightType;
const int MaxVertexNum=10;
const WeightType MaxValue=20000;
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
struct edgenode
{
    int adjvex;
    edgenode *next;
};
typedef edgenode *adjlist[MaxVertexNum];
#include"Graph2.h"

void PATH(adjlist path,int m,int j)
{
  edgenode *p,*q,*s;
  p=path[j];
  while(p!=NULL)
  {
    path[j]=p->next;
    delete p;
    p=path[j];
  }
  p=path[m];
  while(p!=NULL)
  {
    q=new edgenode;
    q->adjvex=p->adjvex ;
    if(path[j]==NULL)
    {
      path[j]=q;
    }
    else    
      s->next=q;
    s=q;
    p=p->next;
  }
  q=new edgenode;
  q->adjvex=j;
  q->next=NULL;
  s->next=q;
}

void Dijkstra(adjmatrix GA,int dist[],adjlist path,int i,int n)
{
  int *s=new int[MaxVertexNum];
  for(int j=0;j<n;j++)
  {
    if(j==i)
      s[j]=1;
    else
      s[j]=0;
    dist[j]=GA[j];
    if((dist[j]<MaxValue)&&(j!=i))
    {
      edgenode *p1=new edgenode;
      edgenode *p2=new edgenode;
      p1->adjvex=i;
      p2->adjvex =j;
      p2->next =NULL;
      p1->next=p2;
      path[j]=p1;
    }
    else
      path[j]=NULL;
  }
  int w;
  int m;
  for(int k=1;k<=n-2;k++){
    w=MaxValue;
    m=i;
    for(j=1;j<n;j++)
      if(s[j]==0&&dist[j]<w){
        w=dist[j];
        m=j;
      }
      if(m!=i)
        s[m]=1;
      else
        break;
      for(j=0;j<n;j++)
        if(s[j]==0&&dist[m]+GA[m][j]<dist[j]){
          dist[j]=dist[m]+GA[m][j];
          PATH(path,m,j);
        }
  }
}

void PrintPath(int dist[], edgenode *path[], int n)
{
  int i,t;
  for(i=1;i<n;i++){
    edgenode *p=path;
    cout<<"V={";
    while(p!=NULL){
      cout<<p->adjvex<<',';
      p=p->next;
    }
    cout<<"}"<<"    length: "<<dist<<endl;
  }
}

void main()
{
    adjmatrix GA;
  int n;
  cout<<"input the points of the graph: ";
  cin>>n;
  InitMatrix(GA);
  CreateMatrix(GA,n);
  PrintMatrix(GA,n);
  cout<<endl;
  cout<<"now print the path and length from v0 to others :"<<endl;
    adjlist path;
    int *dist=new int[MaxVertexNum];
    Dijkstra(GA,dist,path,0,n);
  PrintPath(dist,path,n);
}
[/codes] 阅读全文…