前言：因为要参加竞赛，因此就复习了一下图论方面的知识，总结一下利用Dijkstra算法求最短路径的一般思想与方法，这里先分析下无向图。
一、Dijkstra算法基本思想：
基本思想是： 假设网络中每个点Vj都有一对标号（distj，prev），其中distj就是最短从原点S到Vj的最短路径，prev则是S到J的最短路径的前面一个点。
二、使用条件：
Dijkstra算法的使用条件是：网络中所有的弧圈都非负，即各个点之间的权没有负数存在，这点是显而易见的。
三、代码分析：
下面是一个简单的例子，求一个无向图各个点之间的最短路径。（ps：因为这个图是我自己画的，粗糙请见谅）
下面直接上代码：
//好-Dijkstra算法的流程图-有源程序.doc
/*运行结果:
A->A:0 A->B:3 A->C:8 A->D:8 A->E:7
B->A:3 B->B:0 B->C:5 B->D:6 B->E:4
C->A:8 C->B:5 C->C:0 C->D:4 C->E:6
D->A:8 D->B:6 D->C:4 D->D:0 D->E:2
E->A:7 E->B:4 E->C:6 E->D:2 E->E:0
*/
#include <stdio.h>
//#include "Conio.h"
#define TRUE 1
#define FALSE 0
#define I 9999 // 无穷大
#define N 5 // 城市顶点的数目
int cost[N][N] = { //各点到其他点的弧长二维数组，I表示没有直接联系
{0,3,I,8,I},
{3,0,5,I,4},
{I,5,0,4,7},
{8,I,4,0,2},
{I,4,7,2,0}};
int dist[N]; // 存储当前最短路径长度 dist为起始顶点到该点的最短路径
int v0 = 'A' - 65; // 初始点是 A
int main()
{
int status[N],i,v,w,min,k;
printf("\n任意两个定点之间的最短路径如下：\n\n");
for(k=0;k<N;k++) //做一个N=5重循环
{
// 初始化最短路径长度数据，所有数据都不是最终数据
for (v = 0; v < N; v++)
{
status[v] = FALSE; //初始化，集合s都为假，即都没有永久标号
dist[v] = cost[v0][v];
}
// 首先选v0到v0的距离一定最短，最终数据
status[v0] = TRUE; //把A标记为永久标号
// 寻找另外 N-1 个结点
for (i = 0; i < N-1; i++)
{
min = I; // 初始最短长度无穷大
// 寻找最短的边
for (w = 0; w < N; w++)
{
if (!status[w] && dist[w] < min) //s集合中值为假且最短路径小于min的
{
min = dist[w];
v = w;
}
}
status[v] = TRUE; // 加入新边
for (w = 0; w < N; w++)
{ // 更新 dist[] 数据
if (!status[w] && dist[v] + cost[v][w] < dist[w])
{
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++)
{
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
printf("\n");
v0++;
}
return 0;
}
下面分析下这个程序：
参数设置：
cost[N][N]：各个点之间的弧权。原点分别是从A到E
dist[N]; dist为起始顶点到该点的最短路径。
status ：用来存储具有永久标号的顶点，ture为标号，false为未标号
待续未完。。。。。。