关于图的最短路径问题哦，请大牛们帮小弟改改
程序如下，请教如何修改哦
#include <iostream>
#include <conio>
#include <stdio>
#include <iomanip>
using namespace std;
struct Node
{
int weightvalue;
int weightindex;
};
class queue
{
private:
Node *q;
int front , rear ;
public:
queue()
{
int front = -1 ;
int rear = -1 ;
}
bool isempty()
{
if((front == -1 && rear == -1) || (front > rear))
{
front = rear = -1 ;
return false ;
}
return true ;
}
void enqueue(int x, int y)
{
Node *q;
q = new Node;
q[++rear].weightvalue = x;
q[++rear].weightindex = y;
}
Node dequeue()
{
return q[front++];
}
void makeheap(Node *p, int size)
{
for(int i = size/2; i>=1; i++)
{
int wv = p[i].weightvalue;
int ic = 2*i;
while(ic<=size)
{
if((ic+1) < size && p[ic+1].weightindex > p[ic].weightindex)
{
ic++;
}
if(wv > p[ic].weightvalue)
{
break;
}
p[ic/2].weightindex = p[ic].weightvalue;
ic = 2*ic;
}
p[ic/2].weightindex = wv;
}
}
};
class Matrix : public queue
{
private:
int Mat[20][20], weight[20], path[20];
int n;
public:
Matrix(int m)
{
n = m;
}
void input()
{
cout<<"enter Matrix"<<endl;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin>>Mat[i][j];
}
cout<<endl;
}
cout<<"print the Matrix"<<endl ;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cout<<setw(4)<<Mat[i][j];
}
cout<<endl;
}
}
void makequeue(int s, queue q, int size) //s is the number of sourse node
{
weight[s] = 0;
q.enqueue(weight[s],s);
size++;
for(int i = 1; i<= n; i++)
{
if(i!= s)
{
weight[i] = 999 ;
}
path[i] = 0 ;
}
}
void min_weight(int s)
{
int size;
Node v;
queue a;
Node *R;
R = new Node;
R = a.q;
makequeue(s,a,size);
while(!(a.isempty()))
{
v = dequeue();
size--;
for(int i = 1; i < n; i++)
{
if(Mat[v.weightindex][i]!=0)
{
if((weight[v.weightindex] + Mat[v.weightindex][i]) < (weight[i]))
{
weight[i] = weight[v.weightindex] + Mat[v.weightindex][i];
path[i] = v.weightindex;
a.enqueue(weight[i],i);
size++;
}
}
}
a.makeheap(a.q,size);
}
}
void path_node()
{
int i = 1;
while(path[i] != 0)
cout<<" "<<path[i];
i++;
}
void cost(int s)
{
cout<< "Cost: "<<weight[s]<<endl;
cout<<"******************************"<<endl;
}
};
void main()
{
clrscr();
int k ,m;
cout<<"enter m"<<endl;
cin>>m;
Matrix a(m) ;
a.input() ;
cout<<"*****************"<<endl;
//getch();
//clrscr();
for(int i = 0; i<m; i++)
{
cout<<"wei yong"<<endl;
a.min_weight(i);
cout<<"*****************"<<endl;
for(int j = 0; j<m; j++)
{
if(i!=j)
{
if(++k==20)
{
cout<<"press any key to continue"<<endl;
//getch();
//clrscr();
k=0;
}
cout<<i<<"->"<<j<<endl;
cout<<"------------"<<endl;
cout<<"minimun route :("<<i;
a.path_node();
cout<<")"<<endl;
a.cost(j);
}
}
}
}
[解决办法]
用队列做广搜，出队的结点要标记,邻接点进入队列时要记录它的前驱.
[解决办法]
以前写过一个，不过都是上大学的事儿了。。。
