Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。
基本思想：每次找到离源点最近的顶点，然后以该顶点为中心(过渡顶点)，最终找到源点到其余顶点的最短路。
t=1：令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ). 就是说v_0到v_0的距离是0，其他顶点到v_0的距离为+无穷。t=1时，例5.3上面的步骤(2)(3)并不能体现
t=2：第1步v_0(k=0)获得永久标号，记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj. 步骤(2)最关键，若v_0与v_j之间存在边，则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j<L_j=+无穷。
这里只有v_1,v_2与v_0存在边，所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小，v_1获得永久标号(右上角加点)。
t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样，通过例5.3上面的步骤(2)(3)，得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边，则比较L_1+w_1j与L_j。这里v_1与v_2，v_3，v_,4存在边，
对于v_2, L_1+w_12=1+2=3<L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1)
对于v_3, L_1+w_13=1+7=8<L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1)
对于v_4, L_1+w_14=1+5=6<L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1)
v_5与v_1不存在边，标号不变。步骤(3), 找这些标号L_j最小的顶点，这里v_2标号最小
t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4<L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2)其他不变。步骤(3), L_4=4最小。
t=5: k=4, 同理先找v_4邻接顶点，比较，修改标号，找L_j最小
t=6: 同理
啰嗦的这么多，其实步骤(2)是关键，就是通过比较更新最短路径，右上角标点的就是距离源点最近的顶点，之后每一步就添加一个新的”源点”，再找其他顶点与它的最短距离。
迪杰斯特拉算法(Dijkstra)(百度百科)：
http://baike.baidu.com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_Z7fv8zCUwo7u9LWzeBLl1eV4twGEWLbvd8HjQO6VAvwTs0EcQkISDcezZ27QGWyprSmKlJjosbPNcGKtLYJ5GJsJT6U28koc_FwAlNJAjrVKYUcp3z7bmKewSxlTX8SA0uWKNcu0f0gHmpGa3#4
里面有个动图，更形象地说明了该算法的过程。(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)
#include<stdio.h>#define N 100
#define MaxDist 10000
int mapdist[N][N]
int mindist[N]
void Dijkstra(int n,int c)
{
int i,tag[N],minc,t,j
for(i=1i<=n++i)
{
if(mapdist[c][i]>=0)
mindist[i]=mapdist[c][i]
else
mindist[i]=MaxDist
tag[i]=0
}
for(j=1j<=n++j)
{
minc=MaxDist
for(i=1i<=n++i)
{
if(minc>mindist[i])
{
minc=mindist[i]
t=i
}
}
tag[t]=1
for(i=1i<=n++i)
{
if((mindist[i]>mindist[t]+mapdist[t][i])&&(!tag[i]))
mindist[i]=mindist[t]+mapdist[t][i]
}
}
}
int main()
{
int i,j,n,c
scanf("%d%d",&n,&c)//c为源点
for(i=1i<=n++i)
{
for(j=1j<=n++j)
scanf("%d",&mapdist[i][j])//-1表示不直接连通
}
Dijkstra(n,c)
for(i=1i<=n++i)
printf("%d",mindist[i])
return 0
}
要现写，你的分太少了，至少也200分吧，我给你个模板，时间复杂度为nLOG2(n)：dij邻接阵
#include <algorithm>
#include <deque>
#include <queue>
#include <iostream>
using namespace std
#define MN 1001
#define INF (1<<29)
int graf[MN][MN]
struct node
{
int v
int dis
node(int vv,int dd){v=vvdis=dd}
node(){}
}
bool operator <(const node aa,const node bb)
{
return aa.dis>bb.dis//最小堆
}
int dis[MN]
void dijkstra(int s,int n)//s是源点,[1..n]
{
node tmp
int i,w
for(i=1i<=n++i){dis[i]=INF}
priority_queue <node,deque<node>>Q
Q.push(node(s,0))
for(dis[s]=0!Q.empty())
{
tmp=Q.top()Q.pop()
if(tmp.dis!=dis[tmp.v])continue
for(i=1i<=n++i)
{
w=graf[tmp.v][i]
if(w!=INF&&dis[tmp.v]+w<dis[i])
{
//必要时可保存路径pre[i]=tmp.v
dis[i]=dis[tmp.v]+w
Q.push(node(i,dis[i]))
}
}
}
}
