最短路径算法完整源代码

⑴ 最短路径算法 C语言

#include<stdio.h>

#defineMAXNODE108

intpath[MAXNODE+1][MAXNODE+1]={0};

intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;

fpr=fopen("in.txt","r");/*读取的文件名称in.txt*/
fpw=fopen("out.txt","w");/*path的数据在out.txt中展现*/

while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;

for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;

if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}

for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw,"
");
}

return0;
}

注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！

这是之前的答案的错误之处。

-1表示不通。

具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。

⑵ 寻找最短路径的汇编语言实现源代码是什么(用Dijkstra 算法)

Dijkstra算法Dijkstra算法是典型的最短路径算法，用于计算一个节点的最短路径中的所有其他节点。其主要特点是出发点为中心向外层层扩展，直到扩展到结束日期。 Dijkstra最短路径算法能得出最佳的解决方案，但许多节点，它遍历计算，这样的效率是低的。最短路径算法的
Dijkstra算法是非常有代表性的许多专业课程的基本内容进行了详细的介绍，如数据结构，图论，运筹学，等等。
Dijkstra算法的一般性发言一般有两种方式，永久和临时的标签，开启，关闭表的方式之一，德鲁表示，为了引进和下面的A *算法和D *算法一致，这里是开放的，关闭表。
贪婪的方法，算法策略
大概过程如下：
创建两个表，打开，关闭。
OPEN表保存没有调查之前已产生的所有节点，CLOSED表中记录已访问过的节点。
1。的道路网络的出发点和等待在公开组的检查没有检查点，此点。
2。打开表，以找出从起点最近的点，以确定所有的子节点，这一点，这点上关闭表。
3。遍历访问这个点的子节点。获得这些子节点从子节点到OPEN表的放电的开始点的距离的值。
4。重复步骤2和步骤3，直到OPEN表为空，或找到目标点。
[编辑本段]算法是
包括的文件
定义MAXNUM 765432100的
使用命名空间std;
ifstream的散热片（Dijkstra算法。在“）;
ofstream这样的FOUT（”Dijkstra.out“）;
诠释地图[501] [501];
布尔is_arrived [501];
诠释区[501] [501]，堆栈[501];
整数P，Q，K，路径，源代码，顶点，温度，SetCard
诠释FindMin（）
{
诠释P，温度= 0，MINM = MAXNUM;
（P = 1，P <=顶点，P + +）
（（区[P] MINM）&&（！is_arrived [P] ））
{
MINM区[P]。
温度= P;
}
收益温度;
}
：（ ）
{
的memset（is_arrived，0，大小（is_arrived））;
鳍>>源代码>>顶点;
（P = 1，P <=顶点，P + +）
（Q = 1，Q =顶点，Q + +）
{
鳍>>地图[P] [Q];
（图[ P] [Q] == 0）地图[P] [Q] = MAXNUM;
}
为（P = 1，P <=顶点，P + +）
{ />区[P] =地图[来源] [P];
（区[P]！= MAXNUM）
[P] =源;
其他
[P] = P;
}
is_arrived [来源] = TRUE;
SetCard = 1;

{
温度= FindMin（）;
（Temp! = 0）
{
SetCard SetCard +1;
is_arrived [温度] = TRUE;
（P = 1，P <=顶点，P + +）
（（区[P]>区[温度] +地图[温度] [P]）&&（！is_arrived [P]））
{
区[P] =区[温度] +地图[温度] [P]
[P] =温度;
}
}
其他
突破; BR />}
（SetCard! =顶点）;
（P = 1，P <=顶点，P + +）
（p! =源）
{
FOUT <<“======================== \ n”;
FOUT <<“来源：”<; <资料来源<<“\ n目标：”“P <<'\ n';
（区[P] == MAXNUM）
{
FOUT <<”距离：“< “无限\ n”;
FOUT <<“路径：没办法！”;
}
其他
{
FOUT“距离”：“<<区[P] <<'\ n';
K = 1;
路径= P;
同时（从[路径]！=路径）
{
栈[K] =路径;
路径=从[路径];
K = K +1;
}
FOUT <<“路径：”<（Q = K-1，Q = 1，Q - ）
FOUT“ - >”<<栈[问];
}
FOUT <<“\ ?======================== \ n \ n“;}

fin.close（）;
fout.close（）;
返回0;
}
样品输入
2
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 0??0 55 00 00
00 00 25 55 00 10 00
00 70 50 00 10 00 00
00 00 00 00 00 00 00
样本输出
========================
来源：2
目标：1
距离：20
路径：2 - > 1
==================== ====
========================
来源：
目标：3
距离：25
路径：2 - > 3 ========================

===== ===================
来源：
目标：4
距离：50
路径：2 - > 1 - > ======================== 4

============== =========
来源：
目标：5
距离：50
路径：2 - > 3 - > 5
== ======================
========================
来源：
目标：6
距离：60
路径：2 - > 3 - > 5 - > 6
========= ===============
========================
来源：2
目标：7
距离：无限
路径：没办法！
========================
示例程序和相关子程序如下：
无效的Dijkstra（INT N，INT [ ]距离的int [] iPath标）
{
诠释最短距离，U
INT I，J;
/ /从n个顶点的邻接矩阵的副本可以摆脱行了，是复制前n行的距离[]
（i = 0;我VerNum，我+ +）
{
距离=圆弧[N];
访问= 0;
} / / n个结点访问，因为n个顶点的出发点是
访问[N] = 1;
/ /找到的顶点其他顶点的路线，并且它不是顶点n的开头，没有先前旅游。
/ /相当于u点，这一点是没有的出发点N（i = 0; I <VerNum，我+ +）
{
U = 0

最短距离=否;
为（J = 0; <VerNum; + +）
（访问[J] == 0 &&（距离[J]最短距离））
{
最短距离=距离[J];
ü= J;
}
/ /例如P1871图G6距离=无，无，无，30,100]第一次看的是V2，U = 2
/ /找到结束，的MinDis意味着它无法连接，然后返回。这种情况是相似的V5。

（最短距离==否）返回;
/ /建立一个u个顶点将被用于顶点u，相当于弧[V，U +弧U，W] 。
访问[U] = 1;
/ /找到一个U顶点到所有其他顶点最小的路径实际上是在寻找弧] [U，J，J值在[0， VerNum]。
/ /如果是圆弧，U [I] +凯旋门[U，J] ARC [I，J]，ARC [I，J] =弧[I，U] +凯旋门[U J] <弧[I，J]
/ /的做法，因为距离[]是期望的结果，起始点确定的情况下，那就是：

/ /如果（距离[U] +圆弧[U，J）<=距离[J]：
/ /距离[J]距离[U] + [U，J弧];
/ /保存iPath标[] u点数量;
/ /同样，设置访问量：新发现的路由[J] = 0，经过寻找另一条道路，这条道路可能不利用。 V3
（J = 0; <VerNum; + +）
（访问[J] == 0 &&弧U，J] <&& U！= J） /> {
（（距离[U] +圆弧[U，J）<=距离[J]）
{
距离[J]距离[U] +弧[ U，J];
访问[J] = 0;
iPath标[J] = U;
}
}
}
} / /辅助功能
无效的Prim（），
{
INT I，M，N = 0;
为（i = 0;我VerNum;我+ +）
{
访问= 0;
T =新的TreeNode（）;
T.Text = V;
}
访问[N] + +;
listBox1.Items。添加（V [N]）;
（参观（）> 0）
{
（（M = MinAdjNode（N））！= -1）
{ BR /> T [N]。 Nodes.Add（T [M]）;
N = M;
访问[N] + +;
}
其他
{
?= MinNode（0）;
（N> 0）T [旻]。 Nodes.Add（T [敏]）;
访问[N] + +;
}
listBox1.Items.Add（V [N]）;
} treeView1.Nodes.Add（T [0]）;
}
的无效TopoSort（）
{
INT I，N;
listBox1.Items.Clear（ ）;
栈S =新的堆栈（）;
为（i = 0;我VerNum，我+ +）
访问= 0;
为（= VerNum- 1> = 0; I - ）
（入度（I）== 0）
{
S.Push（I）;
访问+ +; ...... />}
而（S.Count！= 0）
{
N =（INT）S.Pop（）;
listBox1.Items.Add（V [N] ）;
CLEARLINK（N）;
为（i = VerNum-1> = 0; I - ）
（分== 0 &&入度（I）== 0）
{
S.Push（I）;
访问+ +;
}
}
}
无效AOETrave（INT N，树节点TR，W）
{
INT I，W0;
（出度（N）== 0）返回;
（i = 0; <VerNum; + +）
（（W0 =圆弧[N，I]）！= 0）
{
listBox1.Items.Add（V +“\ t”+（W + W0）的ToString（）+“\ t”+ i.ToString（）+“\ t”+ n.ToString（））;
TreeNode的T1 =新的TreeNode（）;
T1.Text = V + “W =”+（W + W0）。的ToString（）+“]”;
TR.Nodes.Add（T1）;
AOETrave（I，T1，W + W0）;
}
}
无效AOE（）
{
INT I，W = 0，M = 1;
TreeNode的T1 =新的TreeNode（）;
为（i = 0; <VerNum;我+ +）
{
访问= 0;
}
T1.Text = V [0];
listBox1.Items.Add（“父母符号显示生成树：“）;
listBox1.Items.Add（”V \ TW \工业贸易署\ TPID“）;
为（i = 0;我VerNum，我+ +）
{
（（W =弧[0，I]）！= 0）
{
listBox1.Items.Add（V +“\ t”+ w.ToString（）+“\ T“+ i.ToString（）+”\ T0“）;
TreeNode的T2 =新的TreeNode（）;
T2.Text = V +”W =“+ w.ToString（）+” “;
AOETrave（I，T2，W）;
listBox1.Items.Add（”\ t \ t树“+ m.ToString
T1.Nodes.Add（ T2），（））;
米+ +;
}
}
treeView1.Nodes.Clear（）;
treeView1.Nodes.Add（T1）;
}
IsZero（）
{
我;
为（i = 0;我VerNum，我+ +）
（LineIsZero （一）> = 0）返回;
返回-1;
}
诠释LineIsZero（N）
{
我
（i = 0; <VerNum;我+ +）
（电弧[N，I] = 0）返回;
返回-1;}

：无效DepthTraverse（）
{
INT I，M;
（i = 0; <VerNum，我+ +）
{
访问= 0; BR /> T =新的TreeNode（）;
T.Text = V
R = 0;
}
而（（M = IsZero（））> = 0）
{
（访问[M] == 0）
{
listBox1.Items.Add（V [M]）;
R [M] = 1 ;}

访问[M] + +;
DTrave（M）;
}
为（i = 0; {
（R == 1）
treeView1.Nodes.Add（T）;
}
}
无效DTrave（N） /> {
我;
（LineIsZero（N）<0）返回;
为（i = VerNum-1> = 0; I - ）
（弧[N] = 0）
{
弧[N，I] = 0;
弧[I，N] = 0;
（访问= = 0）
{
listBox1.Items.Add（V）;
T [N]。 Nodes.Add（T）;
R = 0;
}
访问+ +;
DTrave（I）;
}
} ：无效BreadthTraverse（）
{
INT I，M;
（i = 0; <VerNum，我+ +）
{
访问= 0;
T =新的TreeNode（）;
T.Text = V;
R = 0;
}
而（（M = IsZero（））> = 0 ）
{
（访问[M] == 0）
{
listBox1.Items。添加（V [M]）;
R [M] = 1;
}
访问[M] + +;
BTrave（M）;
} BR />（i = 0;我VerNum，我+ +）
{
（R == 1）
treeView1.Nodes.Add（T）;
}
}
无效BTrave（N）
{
我
队列Q =新的Queue（）;
Q.Enqueue（N）
而（Q.Count！= 0）
{
为（i = 0;我VerNum，我+ +）
{
（电弧N，I] = 0）
{
弧[N，I] = 0;
弧[N] = 0;
（访问== 0）
{
listBox1.Items.Add（V）;
T [N]。 Nodes.Add（T）;
直径= 0;
}
访问+ +;
Q.Enqueue（I）;
}
} BR /> N =（int）的Q.Dequeue（）;
}
}
诠释MinNode（VN）
{
INT I，J，N，米，最小=否;
N = -1，M = -1;
为（i = VN我VerNum，我+ +）
中for（j = 0; J < VerNum; + +）
（电弧[I，J] = &&弧[I，J]闵&&分== 0 &&访问[J] == 1）
{ BR />最小值=弧[I，J]; N = I，M = J;
}
敏=旻= M
返回n;
} BR />诠释MinAdjNode（N）
{
我，敏，米;
最小值=否，M = -1;
（i = 0; I < VerNum，我+ +）
（电弧[N，I] =没有访问&& == 0 &&最小弧[N，I] &&访问[N] == 1）{BR /> BR />最小值=弧[N，I]，M = I;}

返回米;
}
INT访问（）
{
INT I，S = 0;
为（i = 0; <VerNum，我+ +）
（访问== 0）+ +;
返回s;
>}

[编辑本段] Dijkstra算法的Pascal实现：
程序Dijkstra的;
VAR
答：ARRAY [1 .. 100,1 .. 100的整数;
标志：数组[1] .. 100]布尔值;
W，X，N，I，J，分，明尼苏达州：整数;
开始
readln（N）;
我：= 1到n
开始
对于j = 1到n
读（A）;
readln;
结束;
fillchar（标志中，sizeof（标志），假）;
标志[1]：= TRUE;
明尼苏达州：= 1;
为：= 2到n
开始
分： 32767;
W：=明尼苏达州
我：= 1到n做
（W >）和（[W，I] <MIN），然后
开始
分：= [];
明尼苏达州：= I;
结束;
标志[明尼苏达州]：= TRUE;
J： 1到n做
（J >明尼苏达州）和（A [1，明尼苏达州] + A [明尼苏达州，J]，A [1，J）和（标志[J] = FALSE），那么 BR /> A [1，J] = [1，明尼苏达州] + A [明尼苏达州，J];
结束;
我：= 1到n做
写（ [1]）;
年底。

⑶ 最短路径代码

#include<iostream.h>

// 定义 状态代码 及 数据类型
#define NULL 0
#define OK 1
#define ERROR 0
#define INFINITY 255
#define MAX_VERTEX_NUM 20

typedef int Status;
typedef int ElemType;

// ----------------------- 队列结构 -------------------------

// 节点存储结构
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;

// 队列
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

// 初始化队列
Status InitQueue(LinkQueue &Q){
Q.front=Q.rear=new QNode;
if(!Q.front)
return ERROR;
Q.front->next=NULL;
return OK;
}

// 入队
Status EnQueue(LinkQueue &Q,ElemType e){
QueuePtr p=NULL;
p=new QNode;
if(!p)
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}

// 出队
Status DeQueue(LinkQueue &Q,ElemType &e){
QueuePtr p=NULL;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) // 注意当出队后为空队的情况
Q.rear=Q.front;
delete p;
return OK;
}

// 判断是否为空队列
Status EmptyQueue(LinkQueue &Q){
return Q.front==Q.rear?true:false;
}

// 复制队列( Q1 to Q2)
Status CopyQueue(LinkQueue &Q1,LinkQueue &Q2){
int e;
QueuePtr p;
while(!EmptyQueue(Q2)){ // clean Q2
DeQueue(Q2,e);
} // one by one
p=Q1.front->next;
while(p){
e=p->data;
p=p->next;
EnQueue(Q2,e);
}
return OK;
}

// ---------------------- 图的结构：邻接矩阵（有向网） --------------------------//

// 邻接矩阵元素
typedef struct ArcCell{
int adj; // arc value: >0, INFINITY: no link
char *info;
}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 图的结构
typedef struct{
char vexs[MAX_VERTEX_NUM][5]; // 顶点数组
AdjMatrix arcs; // 邻接矩阵
int vexnum; // 图当前的顶点数
int arcnum; // 图当前边的个数
}MGraph;

// 建立邻接图（key=1为有向网，key=0为无向网）
Status CreateUDN(MGraph &G,int vexnum,int edgenum,char *names,char *edges,int key){
int i,j,k,value;
// 输入当前图的顶点数，边个数
G.vexnum=vexnum;
G.arcnum=edgenum;
// 各个顶点数据
for(i=0;i<G.vexnum;++i){
for(j=0;j<4;j++){
G.vexs[i][j]=*names;
names++;
}
G.vexs[i][4]='\0';
}
// 初始化邻接矩阵（全为INFINITY）
for(i=0;i<MAX_VERTEX_NUM;++i){
for(j=0;j<MAX_VERTEX_NUM;++j){
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;

}
}
// 建立邻接矩阵每条边的数值
for(k=0;k<G.arcnum;++k){
i=int(*edges)-48;
edges++;
j=int(*edges)-48;
edges++;
value=(int(*edges)-48)*10;
edges++;
value+=int(*edges)-48;
edges++;
G.arcs[i][j].adj=value;
if(!key){
G.arcs[j][i].adj=value;
}
}
return OK;
}

// 打印出邻接矩阵
void PrintGraph(MGraph &G){
int i,j;
cout<<"\n//--------------- PrintMatrix -----------------//\n\n ";
for(i=0;i<G.vexnum;++i){
cout<<G.vexs[i]<<" ";
}
cout<<endl;
for(i=0;i<G.vexnum;++i){
cout<<"\n\n"<<G.vexs[i]<<" ";
for(j=0;j<G.vexnum;++j){
if(G.arcs[i][j].adj==INFINITY)
cout<<" / ";
else
cout<<" "<<G.arcs[i][j].adj<<" ";
}
}
cout<<"\n\n//--------------- PrintMatrix -----------------//\n";
}

// ---------------------- 求源点v0到各点的最短路径 --------------------------//

void ShortestPath(MGraph &G,int v0){
int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
// 建立队列数组，用以依次储存最短的路径
LinkQueue Q[MAX_VERTEX_NUM];
// 初始化数组
for(i=0;i<G.vexnum;++i){
InitQueue(Q[i]);
D[i]=G.arcs[v0][i].adj;
final[i]=false;
}
final[v0]=true;
// 一个一个循环找出最短距离（共vexnum－1个）
for(i=1;i<G.vexnum;++i){
min=INFINITY;
// 扫描找出非final集中最小的D[]
for(w=0;w<G.vexnum;++w){
if(!final[w] && D[w]<min){
v=w;
min=D[w];
}
}
final[v]=true;
// 更新各D[]数据
for(w=0;w<G.vexnum;++w){
if(!final[w] && G.arcs[v][w].adj+min<D[w]){
D[w]=G.arcs[v][w].adj+min;
CopyQueue(Q[v],Q[w]);
EnQueue(Q[w],v);
}
}
}
// 打印出结果
cout<<"//--------------- ShortestPath -----------------//\n\n";
cout<<" 出发地->目的地\t最短距离\t详细路径\n\n";
for(i=0;i<G.vexnum;i++){
if(D[i]!=INFINITY){
cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\t"<<D[i]<<" \t\t";
cout<<G.vexs[v0];
while(!EmptyQueue(Q[i])){
DeQueue(Q[i],v);
cout<<" -> "<<G.vexs[v];
}
cout<<" -> "<<G.vexs[i]<<endl;
}else{
cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\tNo path!\n";

}
}
cout<<"\n//--------------- ShortestPath -----------------//\n";
}

void PrintCity(char *names,int vexnum){
int i,j;
cout<<"列表：\n\n";
for(i=0;i<vexnum;++i){
cout<<" "<<i<<"-";
for(j=0;j<4;j++){
cout<<*names;
names++;
}
cout<<" ";
}
cout<<"\n请选择出发地点 >";
}

void main(){
MGraph G;

// 图的结构数据
char *edges,*names;
int vexnum,arcnum,city,kind;
vexnum=6;
arcnum=10;
names="A1 A2 A3 A4 A5 A6";
edges="";

do{
PrintCity(names,vexnum);
cin>>city;
cout<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－无向图矩阵 3－有向图矩阵\n4－选择地点 5－退出\n\n请选择操作 >";
do{
cin>>kind;
if(kind>=0 && kind <=3){
CreateUDN(G,vexnum,arcnum,names,edges,kind%2);
switch(kind/2){
case 0:ShortestPath(G,city);
break;
case 1:PrintGraph(G);
break;
}
}
cout<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－无向图矩阵 3－有向图矩阵\n4－选择地点 5－退出\n\n请选择操作 >";
}
while(kind<4);
}
while(kind<5);
}

⑷ 求！最短路径算法 Dijkstra 用C语言编出来

Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪

/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图，有一个特异的顶点s称为缘。
单源最短路径问题，或者称为最短路径问题，是要确定从s到V中没一个其他
顶点的距离，这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给我了c++下的源代码！ --by 伟伟猪
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;}
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/

⑸ 严蔚敏的数据结构（C语言版）最短路径算法 代码段：p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什么意思

二维数组P中保存的是v0到各个点的最短路径。在v行中，值为true的列连起来，就是v0到v的最短路径。因为v0到w点的最短路径是v0到v的最短路径在加上<v,w>，所以w列先复制所有的v列的值，然后在将p[w][w]=true。此时w行中所有值为true列，就是v0到w的最短路径

⑹ 求c语言最短路径算法

#include <iostream>
using namespace std;

const int maxnum = 100;
const int maxint = 999999;

// 各数组都从下标1开始
int dist[maxnum]; // 表示当前点到源点的最短路径长度
int prev[maxnum]; // 记录当前点的前一个结点
int c[maxnum][maxnum]; // 记录图的两点间路径长度
int n, line; // 图的结点数和路径数

// n -- n nodes
// v -- the source node
// dist[] -- the distance from the ith node to the source node
// prev[] -- the previous node of the ith node
// c[][] -- every two nodes' distance
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
bool s[maxnum]; // 判断是否已存入该点到S集合中
for(int i=1; i<=n; ++i)
{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用过该点
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;

// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
// 注意是从第二个节点开始，第一个为源点
for(int i=2; i<=n; ++i)
{
int tmp = maxint;
int u = v;
// 找出当前未使用的点j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!s[j]) && dist[j]<tmp)
{
u = j; // u保存当前邻接点中距离最小的点的号码
tmp = dist[j];
}
s[u] = 1; // 表示u点已存入S集合中

// 更新dist
for(int j=1; j<=n; ++j)
if((!s[j]) && c[u][j]<maxint)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}

// 查找从源点v到终点u的路径，并输出
void searchPath(int *prev,int v, int u)
{
int que[maxnum];
int tot = 1;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp != v)
{
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=1; --i)
if(i != 1)
cout << que[i] << " -> ";
else
cout << que[i] << endl;
}

int main()
{
freopen("input.txt", "r", stdin);
// 各数组都从下标1开始

// 输入结点数
cin >> n;
// 输入路径数
cin >> line;
int p, q, len; // 输入p, q两点及其路径长度

// 初始化c[][]为maxint
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
c[i][j] = maxint;

for(int i=1; i<=line; ++i)
{
cin >> p >> q >> len;
if(len < c[p][q]) // 有重边
{
c[p][q] = len; // p指向q
c[q][p] = len; // q指向p，这样表示无向图
}
}

for(int i=1; i<=n; ++i)
dist[i] = maxint;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
printf("%8d", c[i][j]);
printf("
");
}

Dijkstra(n, 1, dist, prev, c);

// 最短路径长度
cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;

// 路径
cout << "源点到最后一个顶点的路径为: ";
searchPath(prev, 1, n);
}

⑺ 求floyd最短路径算法，c语言代码；

就是一个三重循环，核心代码就这几行
for(k=0;k<n;k++)
{

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A[i][j]>(A[i][k]+A[k][j]))

{

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;

}
}