本文的文字部分转载自博客园，但由于其Dijkstra算法的代码存在一些问题，故特修改了一版该算法，更新上去。供大家参考。
本文相关的习题：
试举例说明如果允许带权有向图中某些边的权为负实数，则Dijkstra算法不能正确求得从源到所有其他顶点的最短路径长度。
Dijkstra算法
算法流程：
(a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞；
(b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；
(c) 修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替。
(d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。
特点：总是按照从小到大的顺序求得最短路径。
假设一共有N个节点，出发结点为s，需要一个一维数组prev[N]来记录前一个节点序号，一个一维数组dist[N]来记录从原点到当前节点最短 路径（初始值为s到Vi的边的权值，没有则为+∞），一个二维数组weights[N][N]来记录各点之间边的权重，按以上流程更新prev[N]和 dist[N]。
参考代码：
//第四章：贪心算法
//////////////////////////////////////////////////////////////////////////
//FUNCTION: Dijkstra 4.4 单源最短路径问题, P105
//INPUT:
// 带权有向图G=(V, E)
// V = {1, 2, …, n}, 顶点v是源点
// c是一个二维数组，c[i][j]表示边(i, j )的权，当<i, j> 属于E时，c[i][j]是一个大数(无穷大）
// dist[i]表示当前从源点到顶点的i 的最短路径长度.
//OUTPUT:
// 路径数组prev[]
//////////////////////////////////////////////////////////////////////////
#ifndef MAXINT
#define MAXUINT ((unsigned)~((unsigned)0))
#define MAXINT ((int)(MAXUINT >> 1))
#define MININT ((int)~MAXINT)
#endif
void dijkstra(int n , int v, int dist[], int perv[], int** c)
{
bool *s = new bool[n + 1];
for (int i = 1; i <= n; i ++)
{
dist[i] = c[v][i];
s[i] = false;
if (dist[i] == MAXINT)
perv[i] = 0;
else
perv[i] = v;
}
dist[v] = 0;
s[v] = true;
for (int i = 0; i < n; i ++)
{
int temp = MAXINT;
int u = v;
for (int j = 1; j <= n; j ++)
{
if ((!s[j]) && dist[j] < temp)
{
u = j;
temp = dist[j];
}
if (u == v) break;
s[u] = true;
for (int j = 1; j <= n; j ++)
{
int newdist = dist[u] + c[u][j];
if (newdist <dist[j])
dist[j] = newdist;
perv[j] = u;
}
}
}
}
Bellman-Ford算法
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w 是边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从 源点s到图G的任意顶点v的最短路径d[v]。
Bellman-Ford算法流程分为三个阶段：
（1）初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;
（2）迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
（3）检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
算法描述如下：
Bellman-Ford(G,w,s) ：boolean //图G ，边集 函数 w ，s为源点
1 for each vertex v ∈ V（G） do //初始化 1阶段
2 d[v] ←+∞
3 d[s] ←0; //1阶段结束
4 for i=1 to |v|-1 do //2阶段开始，双重循环。
5 for each edge（u,v） ∈E(G) do //边集数组要用到，穷举每条边。
6 If d[v]> d[u]+ w(u,v) then //松弛判断
7 d[v]=d[u]+w(u,v) //松弛操作 2阶段结束
8 for each edge（u,v） ∈E(G) do
9 If d[v]> d[u]+ w(u,v) then
10 Exit false
11 Exit true
适用条件和范围：
1.单源最短路径(从源点s到其它所有顶点v);
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3.边权可正可负(如有负权回路输出错误提示);
4.差分约束系统;
#include <stdio.h>
#include <stdlib.h>
/* Let INFINITY be an integer value not likely to be
confused with a real weight, even a negative one. */
#define INFINITY ((1 << 14)-1)
typedef struct
{
int source;
int dest;
int weight;
} Edge;
void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
{
int *distance =(int*) malloc(nodecount*sizeof(int));
int i, j;
for (i=0; i < nodecount; ++i)
distance[i] = INFINITY;
distance[source] = 0;
for (i=0; i < nodecount; ++i)
{
int nbChanges = 0;
for (j=0; j < edgecount; ++j)
{
if (distance[edges[j].source] != INFINITY)
{
int new_distance = distance[edges[j].source] + edges[j].weight;
if (new_distance < distance[edges[j].dest])
{
distance[edges[j].dest] = new_distance;
nbChanges++;
}
}
}
// if one iteration had no impact, further iterations will have no impact either
if (nbChanges == 0) break;
}
for (i=0; i < edgecount; ++i)
{
if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight)
{
puts(“Negative edge weight cycles detected!”);
free(distance);
return;
}
}
for (i=0; i < nodecount; ++i)
{
printf(“The shortest distance between nodes %d and %d is %d\n”, source, i, distance[i]);
}
free(distance);
return;
}
int main(void)
{
/* This test case should produce the distances 2, 4, 7, -2, and 0. */
Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
{2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
{4,0, 6}, {4,2, 7}};
BellmanFord(edges, 10, 5, 4);
return 0;
}