返回信息流#include <iostream>
#include <queue>
#define MAX_EDGE 30
#define MAX_VERTEX 10
#define INFINITE 0x7fffffff
#define AL_END -1
using namespace std;
struct Vertex
{
int vertex;
int cost;
};
bool operator < (const Vertex &a, const Vertex &b)
{
return a.cost > b.cost;
}
struct AlEdge
{
int next;
int vertex;
int cost;
};
class AlGraph
{
public:
int source;
int destination;
int edgeNum;
int vertexNum;
int allCost;
void Dijkstra();
private:
AlEdge edge[MAX_EDGE];
priority_queue<Vertex> nextVertexQueue;
int alVertex[MAX_VERTEX];
bool vertexDealed[MAX_VERTEX];
void initialize();
void geteData();
};
void AlGraph::geteData()
{
cout << "Please input the number of vertex: ";
cin >> vertexNum;
cout << "Please input the number of edge: ";
cin >> edgeNum;
cout << "Please input the source: ";
cin >> source;
cout << "Please input the destination: ";
cin >> destination;
cout << "Please input the edges.(source, destination, cost.)" << endl;
int s, d, c;
int ip = 0;
for (int i = 0; i < edgeNum; i++)
{
cin >> s >> d >> c;
edge[ip].next = alVertex[s];
edge[ip].vertex = d;
edge[ip].cost = c;
alVertex[s] = ip++;
}
}
void AlGraph::initialize()
{
memset(alVertex, AL_END, sizeof(alVertex));
memset(vertexDealed, 0, sizeof(vertexDealed));
allCost = 0;
while (!nextVertexQueue.empty())
{
nextVertexQueue.pop();
}
geteData();
}
void AlGraph::Dijkstra()
{
initialize();
Vertex currentVertex;
currentVertex.cost = 0;
currentVertex.vertex = source;
nextVertexQueue.push(currentVertex);
while (!nextVertexQueue.empty())
{
currentVertex = nextVertexQueue.top();
nextVertexQueue.pop();
if (currentVertex.vertex == destination)
{
break;
}
if (vertexDealed[currentVertex.vertex])
{
continue;
}
vertexDealed[currentVertex.vertex] = true;
Vertex nextVertex;
for (int i = alVertex[currentVertex.vertex]; i != AL_END; i = edge[i].next)
{
if (!vertexDealed[edge[i].vertex])
{
nextVertex.vertex = edge[i].vertex;
nextVertex.cost = currentVertex.cost + edge[i].cost;
nextVertexQueue.push(nextVertex);
}
}
}
if (currentVertex.vertex == destination)
{
allCost = currentVertex.cost;
}
else
{
allCost = INFINITE;
}
}
int main()
{
AlGraph test;
test.Dijkstra();
cout << "The smallest cost is: " << test.allCost << endl;
return 0;
}
自己动手写了一个矩阵型的D算法，于是想找一找邻接表版本的，结果看到了这篇Blog，推了好几遍实在不能理解，希望各位大大帮帮忙
这是一条镜像帖。来源：北邮人论坛 / cpp / #89377同步于 2015/11/4
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
[问题]一个邻接表实现Dijkstra算法的方法，实在是看不懂，求教
lycoris000
2015/11/4镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
【 在 Vampire 的大作中提到: 】
: lz 也不说下哪里看不懂啊，是要大家把所有代码注释一遍么
: 数据结构实现看不懂就先看书
: 语言相关的问题看不懂就查文档
不好意思，看不懂的地方写在了最后一行。。可能被无视了，就是说，这个Dijkstra算法，它比较现阶段路径长和添加新的路径长时的判断不知道在哪里T T，以及初始化邻接表的时候，alVertex[]的含义这两点
每轮扩展路径的时候，从优先队列里面取了当前 cost 最小的点继续扩展
alVertex 保存与某个点相邻的一条边的 id，相当于一个链表头，然后据此不断从 edge[i].next 取得所有相邻的边
【 在 lycoris000 的大作中提到: 】
:
: 不好意思，看不懂的地方写在了最后一行。。可能被无视了，就是说，这个Dijkstra算法，它比较现阶段路径长和添加新的路径长时的判断不知道在哪里T T，以及初始化邻接表的时候，alVertex[]的含义这两点
受教了，谢谢
【 在 Vampire (Vampire) 的大作中提到: 】
: 每轮扩展路径的时候，从优先队列里面取了当前 cost 最小的点继续扩展
: alVertex 保存与某个点相邻的一条边的 id，相当于一个链表头，然后据此不断从 edge[i].next 取得所有相邻的边