算法思想：（单源最短路径）
- 1个点到所有其他点的最短路径
- 查找顶点到其他顶点的最短路径，无法到达的记为+∞，找到最小的，就找到了最短路径的顶点
- 查看上一轮找到的最小点到达其他点的最小值，找到最短路径的顶点。
- 以此类推
- trivial relax：无穷大 ==> 具体数字
- non-trival relax：具体数字 ==> 具体数
参考：https://www.bilibili.com/video/av36886088
运行效果：
step = 1, minw = 0, pacost[0] = 0.00
trival relax: pacost[1] = inf ==> 1.00
trival relax: pacost[3] = inf ==> 2.00
step = 2, minw = 1, pacost[1] = 1.00
trival relax: pacost[2] = inf ==> 4.00
step = 3, minw = 3, pacost[3] = 2.00
trival relax: pacost[2] = 4.00 ==> 3.00
step = 4, minw = 2, pacost[2] = 3.00
visited: {1, 1, 1, 1}
parent: {-1, 0, 3, 0}
pacost: {0.00, 1.00, 3.00, 2.00}
代码：
Dijkstra.c
#include <stdio.h>
#include <stdlib.h>
#include "WeGraph.h"
void DijkstraPrim(Graph g, int nV, int nE, Vertex src, char alg);
int main(){
Graph g = newGraph(4);
Edge e = newEdge(0, 1, 1);
insertEdge(e, g);
e = newEdge(1, 2, 3);
insertEdge(e, g);
e = newEdge(2, 3, 1);
insertEdge(e, g);
e = newEdge(3, 0, 2);
insertEdge(e, g);
DijkstraPrim(g, 4, 4, 0, 'd');
return 0;
}
int *mallocArray(int numV) {
int *array = malloc(numV * sizeof(int));// l
if (array == NULL) { // o
fprintf(stderr, "Out of memory
"); // c
exit(1); // a
} // l
int i; // f
for (i=0; i<numV; i++) { // u
array[i] = UNVISITED; // n
} // c
return array; // t
}
float *mallocFArray(int numV) {
float *array = malloc(numV * sizeof(float));// l
if (array == NULL) { // o
fprintf(stderr, "Out of memory
"); // c
exit(1); // a
} // l
int i; // f
for (i=0; i<numV; i++) { // u
array[i] = MAXWEIGHT; // n
} // c
return array; // t
}
void showArray(char *desc, int *array, int numV) {
int i; // l
printf("%s: {", desc); // o
for (i=0; i<numV; i++) { // c
printf("%d", array[i]); // a
if (i <= numV-2) { // l
printf(", "); // f
} // u
} // n
printf("}
"); // c
return; // t
}
void showFArray(char *desc, float *array, int numV) {
int i; // l
printf("%s: {", desc); // o
for (i=0; i<numV; i++) { // c
printf("%0.2f", array[i]); // a
if (i <= numV-2) { // l
printf(", "); // f
} // u
} // n
printf("}
"); // c
return; // t
}
void DijkstraPrim(Graph g, int nV, int nE, Vertex src, char alg) {
// the last parameter arg is set by main, and is:
// 'd' for Dijkstra or
// 'p' for Prim
int *visited = mallocArray(nV); // initialised to UNVISITED
int *parent = mallocArray(nV); // initialised to UNVISITED
float *pacost = mallocFArray(nV); // floats: initialised to INFINITY
pacost[src] = 0.0;
for (int step = 1; step <= nV; step++) {
printf ("
step = %d, ", step);
Vertex minw = -1;
for (Vertex w = 0; w < nV; w++) { // find minimum cost vertex
if ((visited[w] == UNVISITED) &&
(minw == -1 || pacost[w] < pacost[minw])) {
minw = w;
}
}
printf ("minw = %d, ", minw);
printf ("pacost[%d] = %0.2f
", minw, pacost[minw]);
visited[minw] = VISITED;
for (Vertex w = 0; w < nV; w++) { //
Weight minCost = getWeight(g, minw, w);// if minw == w, minCost = NOWEIGHT
// minCost is cost of the minimum crossing edge
if (minCost != NOWEIGHT) {
if (alg == 'd') { // if DIJKSTRA ...
minCost = minCost + pacost[minw];// add in the path cost
}
if ((visited[w] != VISITED) &&
(minCost < pacost[w])) {
printf (" trival relax: pacost[%d] = %0.2f ", w, pacost[w]);
pacost[w] = minCost;
parent[w] = minw;
printf ("==> %0.2f
", pacost[w]);
}
}
}
}
printf("
");
showArray("visited", visited, nV);
showArray("parent", parent, nV);
showFArray("pacost", pacost, nV);
free(visited);
free(parent);
free(pacost);
return;
}
WeGraph.c
// WeGraph.c: an adjacency matrix implementation of a weighted graph
#include <stdio.h>
#include <stdlib.h>
#include "WeGraph.h"
struct graphRep {
int nV; // #vertices
int nE; // #edges
Weight **edges; // matrix of weights
};
Graph newGraph(int numVertices) {
Graph g = NULL;
if (numVertices < 0) {
fprintf(stderr, "newgraph: invalid number of vertices
");
}
else {
g = malloc(sizeof(struct graphRep));
if (g == NULL) {
fprintf(stderr, "newGraph: out of memory
");
exit(1);
}
g->edges = malloc(numVertices * sizeof(int *));
if (g->edges == NULL) {
fprintf(stderr, "newGraph: out of memory
");
exit(1);
}
int v;
for (v = 0; v < numVertices; v++) {
g->edges[v] = malloc(numVertices * sizeof(int));
if (g->edges[v] == NULL) {
fprintf(stderr, "newGraph: out of memory
");
exit(1);
}
int j;
for (j = 0; j < numVertices; j++) {
g->edges[v][j] = NOWEIGHT;
}
}
g->nV = numVertices;
g->nE = 0;
}
return g;
}
void freeGraph(Graph g) {
if (g != NULL) {
int i;
for (i = 0; i < g->nV; i++) {
free(g->edges[i]); // free the mallocs for each row ...
}
free(g->edges); // now the malloc for the edges array ...
free(g); // now the malloc for the graph rep
}
return;
}
static int validV(Graph g, Vertex v) { // checks if v is in graph
return (v >= 0 && v < g->nV);
}
Edge newEdge(Vertex v, Vertex w, Weight x) { // create an edge from v to w
Edge e = {v, w, x};
return e;
}
void showEdge(Edge e) { // print an edge and its weight
printf("%d-%d: %.2f", e.v, e.w, e.x);
return;
}
int isEdge(Edge e, Graph g) { // 0 if not found, else 1; also fill in wgt
int found = 0;
if (g != NULL) {
if (g->edges[e.v][e.w] != NOWEIGHT) {
found = 1;
}
}
return found;
}
Edge getEdge(Vertex v, Vertex w, Graph g) {
Edge e = {0, 0, 0.0};
if (validV(g, v) || validV(g, w)) {
e.v = v;
e.w = w;
e.x = g->edges[v][w];
}
return e;
}
int cmpEdge(Edge e1, Edge e2) { // comparison based on edge weight
int retval = 0;
if (e1.x < e2.x) {
retval = -1;
}
else if (e1.x > e2.x) {
retval = 1;
}
return retval;
}
void insertEdge(Edge e, Graph g) { // insert an edge into a graph
if (g == NULL) {
fprintf(stderr, "insertEdge: graph not initialised
");
}
else {
if (!validV(g, e.v) || !validV(g, e.w)) {
fprintf(stderr, "insertEdge: invalid vertices %d-%d
", e.v, e.w);
}
else {
if (!isEdge(e, g)) { // increment nE only if it is new
g->nE++;
}
g->edges[e.v][e.w] = e.x;
g->edges[e.w][e.v] = e.x;
}
}
return;
}
void removeEdge(Edge e, Graph g) { // remove an edge from a graph
if (g == NULL) {
fprintf(stderr, "removeEdge: graph not initialised
");
}
else {
if (!validV(g, e.v) || !validV(g, e.w)) {
fprintf(stderr, "removeEdge: invalid vertices
");
}
else {
if (isEdge(e, g) == NOWEIGHT) { // is edge there?
g->edges[e.v][e.w] = NOWEIGHT;
g->edges[e.w][e.v] = NOWEIGHT;
g->nE--;
}
}
}
return;
}
Weight getWeight(Graph g, Vertex v1, Vertex v2) { // get Weight: NOWEIGHT if not existing
Edge e = {v1, v2}; // not required, but for consistency
Weight retval = 0.0;
if (g == NULL) {
fprintf(stderr, "getWeight: graph not initialised
");
}
else {
if (!validV(g, e.v) || !validV(g, e.w)) {
fprintf(stderr, "getWeight: invalid vertices
");
}
else {
retval = g->edges[e.v][e.w];
}
}
return retval;
}
void showGraph(Graph g) { // print a graph
if (g == NULL) {
printf("NULL graph
");
}
else {
printf("V=%d, E=%d
", g->nV, g->nE);
int i;
for (i = 0; i < g->nV; i++) {
int nshown = 0;
int j;
for (j = 0; j < g->nV; j++) {
if (g->edges[i][j] != NOWEIGHT) {
printf("%d %d:%.2f ", i, j, g->edges[i][j]);
nshown++;
}
}
if (nshown > 0) {
printf("
");
}
}
}
return;
}
WeGraph.h
// WeGraph.h: an interface for a weighted graph ADT
#include <math.h>
typedef float Weight; // define a WEIGHT
#define NOWEIGHT -1.0
#define MAXWEIGHT INFINITY
typedef int Vertex; // define a VERTEX
#define UNVISITED -1
#define VISITED 1
typedef struct {
Vertex v;
Vertex w;
Weight x;
} Edge;
typedef struct graphRep *Graph; // define a GRAPH
Graph newGraph(int);
void freeGraph(Graph);
void showGraph(Graph);
void insertEdge(Edge, Graph);
void removeEdge(Edge, Graph);
void showEdge(Edge);
int isEdge(Edge, Graph);
Edge newEdge(Vertex, Vertex, Weight);
Edge getEdge(Vertex, Vertex, Graph);
int cmpEdge(Edge, Edge);
Weight getWeight(Graph, Vertex, Vertex);