首页 > Sentiment > 实验9 图的最短路径问题

实验9 图的最短路径问题

2008年11月28日 发表评论 阅读评论 755 views

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]
Graph2.h
[codes=c]
void InitMatrix(adjmatrix G)
{
  int i,j;
  for(i=0;i<MaxVertexNum;i++)
    for(j=0;j<MaxVertexNum;j++)
      if(i==j)
        G[j]=0;
      else
        G[j]=MaxValue;
}

void CreateMatrix(adjmatrix G, int n)
{
  char *s=new char[100];
  cerr<<"please input the adjmatrix :"<<endl;
  cin>>s;
  istrstream sin(s);
  char c1,c2,c3;
  int i,j;
  WeightType w;
  sin>>c1;
  do{
    sin>>c1>>i>>c2>>j>>c3>>w;
    G[j]=w;
    sin>>c1;
    if(c1=='}')
      break;
  }while(1);
}

void PrintMatrix(adjmatrix G, int n)
{
  int i,j;
  cout<<"V={";
  for(i=0;i<n-1;i++)
    cout<<i<<',';
  cout<<n-1<<'}'<<endl;
  cout<<"E={";
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      if(G[j]!=0&&G[j]!=MaxValue)
        cout<<'<'<<i<<','<<j<<'>'<<G[j]<<',';
  cout<<'}'<<endl;
}
[/codes]

分类: Sentiment 标签: , , ,
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :cool: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O