解决单源最短路径问题的一般方法是Dijkstra算法，该算法是贪婪算法的典型应用。其基本思想是对有向赋权图以开始顶点出发，逐层外扩（即广度优先搜索），以寻找当前最短路径。
1、从顶点V1为出发顶点，其距离dv1=0，为最小值，因此选择处理v1,将v1设为已知，与V1连接的顶点为v2、v4。其距离均小于当前dv4 和dv2的无穷大，因此更新：dv4=1,dv2=2;
2、选择当前距离最小未知顶点v4，,将v4设为已知。与v4邻接顶点为v3,v5,v6,v7，更新距离：dv3=1+2=3,dv6=1+8=9,dv7=1+4=5,dv5=1+2=3;(因为新值均小于他们的当前值无穷大，因此需要更新)。
3、选择当前距离最小未知顶点为v2,将v2设为已知。 与v2连接点为v4,但v4已知，因此不需更新。连接点v5,由于dv2+10=12>dv5=3，因此不更新dv5。
4、选择当前距离最小未知顶点v5,设为已知。更新其连接点：v7,但因为dv5+6=3+6> dv7=5，因此不用更新。
5、选择当前距离最小未知顶点v3,设为已知，且更新v6距离dv6=6。
6、最后选择v6，设为已知。此时所有顶点处理完毕。
实现代码如下：
/*Dijkstra 算法声明*/
typedef int Vertex;//顶点
typedef int DistType;
struct List;
/*每个顶点对应一个TaleEntry结构*/
struct TableEntry
{
Lsit Header;//邻接顶点链表
int Know;//表示该顶点是否已经已知（即处理过了）
DistType Dist;//起点到该点的权值距离
Vertex Path;//到达该点的前一顶点
};
/*顶点标号从0开始*/
#define NotAvertex (-1)
#define INF 0x7fffffff
typedef struct TableEntry Table[NumVertex];
/*表初始化*/
void InitTable(Vertex start,Graph G,Table T)
{
int i；
ReadGraph(G,T);//将图读入到连接表中
for(i=;i<NumVertex;++i)
{
T[i].Know=false;
T[i].Dist=INF;
T[i].Path=NotAvertex;
}
T[start].Dist=;
}
/*递归打印到给定顶点的最短路径*/
void PrintPath(Vertex V,Table T)
{
if(T[V].Path!=NotAvertex)//如果还有前向顶点，则先打印前面的顶点
{
PrintPath(T[V].Path,T);
printf(" to ");
}
printf(" %d ",V);
}
/*Dijkstra 算法*/
void Dijkstra(Table T)
{
Vertex V,W;
for(; ;)
{
V=smallest unknow distance vertex;//取当前未知顶点中的权值最小的顶点
if(V==NotAvertex)
break;
T[V].know=true;
for each W adjacent to V //调整连接到V的所有顶点W的距离值
if(!T[W].know) //仅更新未知顶点
{
if(T[W].Dist>T[V].Dist+Cvw)//仅当新的距离值小于当前距离值时才更新它，并同时更新其前向节点
{
T[W].Dist=T[V].Dist+Cvw;
T[w].Path=V;
}
}
}
只要没有负值边，以上算法总能正确完成。
性能分析：
需要注意的是，如果用优先队列来实现查找最小距离时，每次将更新的dw要更新到原队列中对应点的d值，但是用二叉堆实现的优先队列的Find操作低效的。因此可以采取重复插入到优先队列的办法，这时队列中将可能存在一个点的多个版本，因此在每次DeleteMin操作把最小点从队列删除时，必须检查以肯定该点是未知的，从而避免对已知点重复处理，如果该点为已知，则丢弃，从新DeleteMin。这种实现方法不会增加时间界，但是会增加空间需求。当然可以选用其他的数据结构实现的优先队列，比如斐波那契堆等。