最初看严蔚敏老师的《数据结构》一书时，便感觉Dijkstra (读作['daik stra])和Prim这两个算法几乎一摸一样，后来看到李清勇老师的《算法设计与问题求解》一书中对两中算法的比较，才知道两种算法的异同点。
关于Dijkstra的念法，请看如下地址说明：
https://www.cnblogs.com/daxia319/archive/2010/10/16/1853178.html
Dijkstra 算法是求连通图中起始点和每一个点之间的最短路径，而prim算法是求连通图的最小生成树，也就是生成树的最短路径之和。
假设图中所有顶点的集合为V，Dijkstra是先把起始顶点 u 0 u_0 u0加入集合S使得 S = { u 0 } S=\{u_0\} S={ u0}，然后从剩下的顶点集合V-S中寻找如下条件的最短的边：该边的一个顶点位于集合S，一个顶点位于集合V-S，这样一直循环直到所有的顶点V都在S中。
而Prim算法是在所有的边中寻找最短的边，同时如果该边的两个顶点都不在S中，就加入集合S，然后继续寻找其他的边，知道所有的顶点V都在集合S中。
在实现上，两者的思路基本一致，都要维护一个最短路径数组。在每次加入一个顶点后，都会计算并更新最短路径数组的每个下标值。所不同的是，Prim算法每次更新时，是将S集合中所有的顶点看作一个顶点A，计算的V-S 集合中顶点和顶点A的距离，而Dijkstra 是计算的起始点和新加入顶点的距离。
Dijkstra代码示例：
#include "dijkstra.h"
#include "graph.h"
//from 0
//plus
int dijkstra(GRAPH * g) {
int num = 0;
unsigned __int64 * cost = new unsigned __int64[g->vertex];
int * visit = new int[g->vertex];
int* vertex = new int[g->vertex];
int* v = new int[g->vertex];
int idx = 0;
for (int i = 0; i < g->vertex; i++) {
idx = num * g->vertex + i;
if (g->element[idx].e) {
cost[i] = g->element[idx].e;
}
else {
cost[i] = -1;
}
visit[i] = 0;
vertex[i] = 0;
v[i] = 0;
}
int pos = 1;
for (num = pos; num < g->vertex; num++) {
int n = 0; //must be in circle
unsigned __int64 t = 0xffffffffffffffff; //must be in circle
for (int j = 0; j < g->vertex; j++)
{
if (visit[j] == 0) {
if (cost[j] < t) {
t = cost[j];
n = j;
}
}
}
//vertex[num] = n;
v[num] = t;
for (int k = 0; k < g->vertex; k++) {
if (visit[n] == 0) {
idx = n * g->vertex + k;
int srcpos = num * g->vertex + k;
if (g->element[idx].e && g->element[srcpos].e) {
if (cost[k] > g->element[idx].e + g->element[srcpos].e) {
cost[k] = g->element[idx].e + g->element[srcpos].e;
vertex[k] = n;
}
}
}
}
visit[n] = 1;
}
return 0;
}
void testDijkstra() {
GRAPH* g = genGraph(10,-1);
dijkstra(g);
return;
}
Prim代码示例：
#include "prim.h"
#include "graph.h"
int prim(GRAPH* g) {
int num = 0;
unsigned __int64* cost = new unsigned __int64[g->vertex];
int* visit = new int[g->vertex];
int* vertex = new int[g->vertex];
int* v = new int[g->vertex];
int idx = 0;
for (int i = 0; i < g->vertex; i++) {
idx = num * g->vertex + i;
if (g->element[idx].e) {
cost[i] = g->element[idx].e;
}
else {
cost[i] = -1;
}
visit[i] = 0;
vertex[i] = 0;
v[i] = 0;
}
visit[0] = 1;
vertex[0] = 0;
v[0] = 0;
int pos = 1;
for (num = pos; num < g->vertex; num++) {
int n = 0; //must be in circle
unsigned __int64 t = 0xffffffffffffffff; //must be in circle
for (int j = 0; j < g->vertex; j++)
{
if (visit[j] == 0) {
if (cost[j] < t) {
t = cost[j];
n = j;
}
}
}
//vertex[num] = n;
v[num] = t;
for (int k = 0; k < g->vertex; k++) {
if (visit[n] == 0) {
idx = n * g->vertex + k;
if (g->element[idx].e) {
int srcpos = num * g->vertex + k;
if (cost[k] > g->element[idx].e) {
cost[k] = g->element[idx].e;
vertex[k] = n;
}
}
}
}
visit[n] = 1;
}
return 0;
}
void testPrim() {
GRAPH* g = genGraph(5, -1);
prim(g);
return;
}
