#include<iostream>
#include<math.h>
#include<cstdlib>
#include<cstring>
#define ElemType int
#define MaxSize 10
#define Infinite 10000
using namespace std;
class List
{
public:
List *head;
List *next;
ElemType elem;
List();
void Insert(ElemType data);
void delet();
};
List::List()
{
head = (List*) malloc (sizeof(List));
if(!head)
exit(OVERFLOW);
head->next = NULL;
}
void List::Insert(ElemType data)
{
List *p, *q;
p = head;
while(p->next)
p = p->next;
q = (List*) malloc (sizeof(List));
q->elem = data;
q->next = NULL;
p->next = q;
}
void List::delet()
{
head->next = NULL;
}
class Graph:public List
{
private:
int **arc;//存储矩阵
int numvex;//点数
int numedge;//边数
int v0;//起始点
int *distance;//距离数组
bool *Final;//判断数组
List *list;
public:
Graph();
void Dijkstra();
void print();
};
Graph::Graph()
{
cout<<"请输入点数:";
cin>>numvex;
cout<<"请输入边数:";
cin>>numedge;
arc = new int*[numvex];
for(int i=0;i<numvex;i++)
arc[i] = new int[numvex];
for(int i=0;i<numvex;i++)
for(int j=0;j<numvex;j++)
if(i==j)
arc[i][j] = 0;
else
arc[i][j] = Infinite;
int v1, v2;
int weight;
for(int i=0;i<numedge;i++)
{
cout<<"请按顺序输入边的两顶点(v1, v2):";
cin>>v1;
cin>>v2;
cout<<"请输入边的权值:";
cin>>weight;
arc[v1][v2] = weight;
}
cout<<"请输入起始点:";
cin>>v0;
distance = new int[numvex];
Final = new bool[numvex];
memset(Final, false, sizeof(Final));
list = new List[numvex];
for(int i=0;i<numvex;i++)
distance[i] = arc[v0][i];
}
void Graph::Dijkstra()
{
Final[v0] = true;
for(int i=1;i<numvex;i++)
{
int min = Infinite;
int min_vex;
for(int j=0;j<numvex;j++)
if(Final[j]==false&&distance[j]<min)
{
min_vex = j;
min = distance[j];
}
Final[min_vex] = true;
for(int j=0;j<numvex;j++)
if(distance[j]>distance[min_vex]+arc[min_vex][j])
{
distance[j] = distance[min_vex]+arc[min_vex][j];
list[j].Insert(min_vex);
}
}
}
void Graph::print()
{
List *p;
for(int i=0;i<numvex;i++)
{
if(distance[i]<Infinite/2)
{
cout<<v0<<"->";
p = list[i].head->next;
while(p)
{
cout<<p->elem<<"->";
p = p->next;
}
cout<<i;
cout<<" distance:"<<distance[i];
cout<<endl;
}
else
{
cout<<v0<<"->"<<i;
cout<<" distance:"<<"Infinite";
cout<<endl;
}
}
}
int main()
{
Graph g;
g.Dijkstra();
g.print();
}