因为是稀疏图，所以应当选择邻接表来存储
构造一个邻接表
这只是我的构造方法，有很多种更好的构造方法，大家可以自己去构造
typedef int vertex;
typedef int WeightType; //邻接表中单链表的节点
typedef struct ArcNode
{
int to;
WeightType weight;
struct ArcNode *next;
}ArcNode; //顶点， 存放顶点信息和一个指向第一个与该顶点相连的节点
typedef struct Node
{
vertex id;
ArcNode *first;
}Node; //图
typedef struct LGraph
{
int v, e;
Node G[MaxVertexNum];
}LGraph;
因为是稀疏图，所以我们应该使用最小堆来选择当前最小的dist节点
//稀疏图我们使用一个最小堆的数据结构
//这里我们自定义一个最小堆 void Dijkstra(int dist[], vertex path[], LGraph& g, vertex id)
{
//自定义的最小堆, 我们就用c++中的名字
priority_queue q;
//定义是否被收入集合
int collection[MaxVertexNum];
memset(collection, , sizeof(collection)); dist[id] = ;
q.push(id, dist[id]);
while(!q.empty())
{
vertex v = q.pop().id;
//将v加入收入集合
collection[v] = ; ArcNode *t = g.G[v].first;
while(t->next)
{
vertex i = t->to;
//这里查找v的所有邻接节点，更新他们的最短距离
//这里的i应该没有被收入，也就是说collection[i] == 0
//因为如果i已经被收入， 并且满足dist[i] > dist[v] + t->weight
//就说明v比i到id的距离更短，所以v应当先被收入，构成矛盾
if(collection[i] == && dist[i] > dist[v] + t->weight)
{
dist[i] = dist[v] + t->weight;
path[i] = v;
//将这个距离加入到最小堆中
q.push(i, dist[i]);
}
}
}
}
新手，欢迎大家找错误，提意见。