单源最短路径算法
单源最短路径问题是一个经典问题，给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另外，还给定 V 中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
单源最短路径问题的分析过程可以使用 Dijkstra 算法来解决。Dijkstra 算法是一种贪心算法，具有贪心选择性质和最优子结构性质。贪心选择性质是指在每一步选择当前最优的选择，而最优子结构性质是指问题可以分解成规模更小的子问题，最后将这些子问题的解组合成原问题的解。
单源最短路径问题的算法设计可以分为以下几个步骤：
1. 初始化：设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。初始时， S 中仅含有源。设 u 是 G 的某一个顶点，把从源到 u 且中间只经过 S 中顶点的路称为从源到 u 的特殊路径，并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。
2. 选择：从 V-S 中取岀具有最短特殊路长度的顶点 u，将 u 添加到 S 中，同时对数组 dist 作必要的修改。
3. 重复：重复选择和添加步骤，直到 S 包含了所有 V 中的顶点。
单源最短路径问题的算法实现可以使用 C++ 语言，使用邻接矩阵来表示带权有向图。下面是一个简单的实现代码：
```c
#include <iostream>
#include <stdlib.h>
using namespace std;
#define MAX 1000000 //充当”无穷大”
#define LEN sizeof(struct V_sub_S)
#define N 5
#define NULL 0
int s; //输入的源点
int D[N]; //记录最短路径
int S[N]; //最短距离已确定的顶点集
const int G[N][N] = { {0, 10, MAX, 30, 100},
{MAX, 0, 50, MAX, MAX},
{MAX, MAX, 0, MAX, 10},
{MAX, MAX, 20, 0, 60},
{MAX, MAX, MAX, MAX, 0} };
typedef struct V_sub_S //V-S 链表
{
int num;
struct V_sub_S *next;
};
struct V_sub_S *create()
{
struct V_sub_S *head, *p1, *p2;
int n = 0;
head = NULL;
p1 = (V_sub_S *)malloc(LEN);
p1->num = s;
head = p1;
for(int i = 0; i < N+1; i++)
{
if(i != s)
{
++n;
if(n == 1)
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = (V_sub_S *)malloc(LEN);
p1->num = i;
p1->next = NULL;
}
}
free(p1);
return head;
}
struct V_sub_S *DelMin(V_sub_S *head, int i)
{
V_sub_S *p1, *p2;
p1 = head;
while(i != p1->num && p1->next != NULL)
{
p2 = p1;
p1 = p1->next;
}
p2->next = p1->next;
return head;
}
void Dijkstra(V_sub_S *head)
{
//实现 Dijkstra 算法
}
```
单源最短路径问题是一个经典问题，可以使用 Dijkstra 算法来解决。Dijkstra 算法具有贪心选择性质和最优子结构性质，是一种经典的贪心算法。
