c算法最短路径_C语言实现最短路问题的算法

㈠最短路径算法 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 用C语言编出来

#include"iostream.h"
#include"stdlib.h"
#define MAXPOINT 3//定义最大的顶点数目

#define limit 32767 //设置没有路径的权代替无穷大

struct record{ //没个顶点的数据结构设置为一个数组队列
int number; //顶点号
int flag; //标志是否从队列中被选过如果为1表示选过为0表示未选
int allpath; //从源点到这个点的当前最短距离（权最小）
}path[MAXPOINT+1];

int cost[MAXPOINT+1][MAXPOINT+1]; //用来表示图的邻接矩阵

void main()
{int i,j,temp,front=1,rear=MAXPOINT,N,minnumber;
//temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾
//N 表示待输入的源点号码 minnumber 表示选中的点的号码
int min=32768; //设置一个初始值
for(i=1;i<=MAXPOINT;i++)
for(j=1;j<=MAXPOINT;j++)
{cout<<"请输入从第"<<i<<"点到第"<<j<<"点的路径长度(权)如果没有路径的话请输入'32767' "<<endl;
cin>>cost[i][j]; //初始化所有点之间的（权）路径值
}

//cout<<"请输入源点号"<<endl; //输入一个起点
//cin>>N;

for(N=MAXPOINT;N>=1;N--)//把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径

{ for(i=front;i<=rear;i++) //初始化每个点的信息
{if(i==N)
path[i].allpath=0;
else
path[i].allpath=limit;
path[i].flag=0;
path[i].number=i;
}

while(rear>=1) //控制循环次数
{for(temp=front;temp<=MAXPOINT;temp++)
{ if(path[temp].allpath<min&&path[temp].flag==0)//选出一个具有最值
//的点

{ minnumber=path[temp].number;
min=path[temp].allpath ;
}

}
min=32768;

path[minnumber].flag=1;//把选中的点的标志变量置1表示已经被选过避免选中

for(i=1;i<=MAXPOINT;i++)//进行类似广度优先搜索，更新最短路径
{if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<path[i].allpath))
path[i].allpath=path[minnumber].allpath+cost[minnumber][i];
}

rear--;//次数减1
}
rear=MAXPOINT; //恢复数组以便于下一点的循环
for(j=1;j<=MAXPOINT;j++)
{ cout<<"第"<<N<<"点到第"<<j<<"点的最短路径长度（权）为";
cout<<path[j].allpath <<endl;
}

}

}

//这个程序可以求出任意一对顶点之间的最短路径，不过这种算法效率还不是很高，还有其他算法待续

㈢如何用C语言实现求迷宫的最短路径

#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定义迷宫，0表示能走的块，1表示不能走，在外围加上一圈不能走的块
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //块的位置
int pre; //本路径中上一块在队列中的下标
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四个方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循环
}
}
}
return 0;
}

void print(int n) //输出路径算法
{
int k=n,j,m=1;
printf("\n");
do //将输出的路径上的所有pre改为-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宫最短路径如下：\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}

㈣ C语言数组求最短路径

#include <stdio.h>
#define M 5 /*行数*/
#define N 5 /*列数*/
#define MaxSize 100 /*栈最多元素个数*/
int mg[M+1][N+1]={ /*一个迷宫,其四周要加上均为1的外框*/
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct
{
int i;int j;int di;
} Stack[MaxSize],Path[MaxSize]; /*定义栈和存放最短路径的数组*/
int top=-1; /*栈指针*/
int count=1; /*路径数计数*/
int minlen=MaxSize; /*最短路径长度*/
void mgpath() /*路径为:(1,1)->(M-2,N-2)*/
{
int i,j,di,find,k;
top++; /*进栈*/
Stack[top].i=1;
Stack[top].j=1;
Stack[top].di=-1;mg[1][1]=-1; /*初始结点进栈*/
while (top>-1) /*栈不空时循环*/
{
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
if (i==M-1 && j==N-1) /*找到了出口,输出路径*/
{
printf("%4d: ",count++);
for (k=0;k<=top;k++)
{
printf("(%d,%d) ",Stack[k].i,Stack[k].j);
if ((k+1)%5==0) printf("\n\t"); /*输出时每5个结点换一行*/
}
printf("\n");
if (top+1<minlen) /*比较找最短路径*/
{
for (k=0;k<=top;k++)
Path[k]=Stack[k];
minlen=top+1;
}
mg[Stack[top].i][Stack[top].j]=0; /*让该位置变为其他路径可走结点*/
top--;
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
}
find=0;
while (di<4 && find==0) /*找下一个可走结点*/
{ di++;
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3:i=Stack[top].i,j=Stack[top].j-1;break;
}
if (mg[i][j]==0) find=1;
}
if (find==1) /*找到了下一个可走结点*/
{ Stack[top].di=di; /*修改原栈顶元素的di值*/
top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;/*下一个可走结点进栈*/
mg[i][j]=-1; /*避免重复走到该结点*/
}
else /*没有路径可走,则退栈*/
{
mg[Stack[top].i][Stack[top].j]=0; /*让该位置变为其他路径可走结点*/
top--;
}
}
printf("最短路径如下:\n");
printf("长度: %d\n",minlen);
printf("路径: ");
for (k=0;k<minlen;k++)
{
printf("(%d,%d) ",Path[k].i,Path[k].j);
if ((k+1)%5==0) printf("\n\t"); /*输出时每5个结点换一行*/
}
printf("\n");
}
void main()
{
printf("迷宫所有路径如下:\n");
mgpath();
}

㈤ C语言实现最短路问题的算法

＃i nclude<stdio.h>
＃i nclude <stdlib.h>
//Dijkstra算法实现函数
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
int i;
int j;
int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值
int *s ;//定义具有最短路径的节点子集s
s = (int *)malloc(sizeof(int) * n);
//初始化最小路径代价和前一跳节点值
for (i = 1; i <= n; i++)
{
dist[i] = cost[v][i];
s[i] = 0;
if (dist[i] == maxint)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = 1;//源节点作为最初的s子集
for (i = 1; i < n; i++)
{
int temp = maxint;
int u = v;
//加入具有最小代价的邻居节点到s子集
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (dist[j] < temp))
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
//计算加入新的节点后，更新路径使得其产生代价最短
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (cost[u][j] < maxint))
{
int newdist = dist[u] + cost[u][j];
if (newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
int j = 0;
int w = u;
int count = 0;
int *way ;
way=(int *)malloc(sizeof(int)*(n+1));
//回溯路径
while (w != v)
{
count++;
way[count] = prev[w];
w = prev[w];
}
//输出路径
printf("the best path is:\n");
for (j = count; j >= 1; j--)
{
printf("%d -> ",way[j]);
}
printf("%d\n",u);
}
//主函数，主要做输入输出工作
void main()
{
int i,j,t;
int n,v,u;

int **cost;//代价矩阵
int *dist;//最短路径代价
int *prev;//前一跳节点空间
printf("please input the node number: ");
scanf("%d",&n);
printf("please input the cost status:\n");

cost=(int **)malloc(sizeof(int)*(n+1));
for (i = 1; i <= n; i++)
{
cost[i]=(int *)malloc(sizeof(int)*(n+1));
}
//输入代价矩阵
for (j = 1; j <= n; j++)
{
for (t = 1; t <= n; t++)
{
scanf("%d",&cost[j][t]);
}
}

dist = (int *)malloc(sizeof(int)*n);
prev = (int *)malloc(sizeof(int)*n);
printf("please input the source node: ");
scanf("%d",&v);
//调用dijkstra算法
Dijkstra(n, v, dist, prev, cost);
printf("*****************************\n");
printf("have confirm the best path\n");
printf("*****************************\n");
for(i = 1; i <= n ; i++)
{
if(i!=v)
{
printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i]);
printf("the pre-node of node %d is node %d \n",i,prev[i]);
ShowPath(n,v,i, dist, prev);
}
}
}

㈥ c语言数据结构最短路径问题代码

直接看代码：

#include<stdlib.h>
#defineMAXVEX10
typedefstructgraph{
intn,e;//顶点数、边数
charvexs[MAXVEX];//顶点数组
intarcs[MAXVEX][MAXVEX];//邻接矩阵
intkind;//类型：0有向图；1无向图；2有向网；3无向网
}MGraph;
voidPrintPath(MGraphG,int*p,inti){
if(p[i]>=0){
PrintPath(G,p,p[i]);//先输出前驱顶点
}
printf("%c",G.vexs[i]);//输出本顶点
}
voidDijkstra(MGraphG,intv){
//用Dijkstra算法求有向网G中序号为v的顶点到
//其余各顶点的最短路径
int*s,*d,*p,i,j,k,min;
if(v<0||v>=G.n){//顶点编号参数错误
printf("DijkstraparameterERROR!v<0Orv>=%d",G.n);
return;
}
s=(int*)malloc(sizeof(int)*G.n);
d=(int*)malloc(sizeof(int)*G.n);
p=(int*)malloc(sizeof(int)*G.n);
for(i=0;i<G.n;i++){//初始化辅助数组，置0
s[i]=0;d[i]=G.arcs[v][i];
if(d[i]!=0)p[i]=v;//v是vi的直接前驱
elsep[i]=-1;//-1表示无直接前驱
}
s[v]=1;d[v]=0;//确定源点自身的最短路径长度
printf("Dijkstra:(Theshortestpathfrom%c:)
",G.vexs[v]);
for(i=0;i<G.n-1;i++){
//确定v到其余n-1个顶点的最短路径
min=32767;k=-1;
for(j=0;j<G.n;j++){
//找出路径长度最小的顶点k
if(!s[j]&&d[j]!=0&&d[j]<min){
k=j;min=d[k];
}
}
if(k<0){//有未能到达的顶点，把它们输出
for(j=0;j<G.n;++j){
if(j==v)continue;
if(s[j]==0){
printf("%c->%c:Nopath.
",G.vexs[v],G.vexs[j]);
}
}
free(s);free(d);free(p);
return;//已完成或出现不连通的顶点
}
s[k]=1;
printf("%c->%c:d=%-5d,p=",G.vexs[v],G.vexs[k],d[k]);
PrintPath(G,p,k);//输出v到i的路径（正序）
printf("
");
for(j=0;j<G.n;j++){
//更新其余顶点的最短路径及前驱
if(!s[j]&&G.arcs[k][j]!=0&&(d[j]==0||d[j]>d[k]+G.arcs[k][j])){
d[j]=d[k]+G.arcs[k][j];p[j]=k;
}
}
}
free(s);free(d);free(p);
}

这是单源的最短路径算法。

㈦求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);
}

㈧ C语言求两点之间的最短路径

#include<graphics.h>
#include<stdio.h>
# define n 6
# define NULL 0
#define UP 72
#define DOWN 80
#define ESC 27
#define Enter 13
int i1=0,j1=3,m1=0,n1=0;
int start=0;
char str2[][100]={"THE INTRODUTION OF THE ROUTINE !",
"AUGMENT THE RELATIVE DATA !",
"SEARCH FOR THE INFORMATION !",
"QUIT THE ROUTINE !"};
char str3[][100]={"THE ROUTINE WAS PROGRAMED IN ",
" 2006--07--10",
"PROGRAMER : ",
"CAO JUN BIN "};

int dd[n+1][n+1], pp[n+1][n+1],a[n];
typedef struct
{int number; int edge[n+1][n+1]; }graph;
graph g;
int maxdist=2000,mindist;
struct viewpoint
{int x; int y; int number; char inf[10]; }bd[n];

struct point
{int number; int x_1; int y_1; }point[n];
typedef struct point f;
struct path
{int V1; int V2; int length; }p[n*n/2];

void mainmenu ();
void con();
void choosepoint() ;
void interface();
void interface1();
void again();
void drawbuilding();
void drawedge();
void floyd(graph g,int m, int dd[n+1][n+1],int pp[n+1][n+1]);
void display(int i,int j,int pp[n+1][n+1],int dd[n+1][n+1]);
void drawpath();
void buildingmap( );
void pathmap( );
main()
{ int gdriver=9,gmode=2;
initgraph(&gdriver,&gmode,"c:\\TURBOC2");
mainmenu();
}

void mainmenu ()
{int a,flag=1,i,j; char c; char str[10]; setbkcolor(BLACK); setcolor(LIGHTGRAY); rectangle(20,20,600,475); settextstyle(4,0,4); setcolor(LIGHTRED); outtextxy(160,70,"THE MAIN MENU "); settextstyle(3,0,1); setcolor(CYAN); outtextxy(160,160,str2[0]); outtextxy(160,200,str2[1]); outtextxy(160,240,str2[2]); outtextxy(160,280,str2[3]); while(flag){ c=getch(); switch(c){case DOWN:i1++;j1++; m1=i1%4;n1=j1%4; con();break; case UP :if(i1==-1)i1=3;if(j1==-1)j1=3; m1=i1%4;n1=j1%4;a=m1;m1=n1;n1=a; con(); i1--;j1--;break; case ESC :flag=0;break; case Enter:cleardevice(); if(m1==0){interface1();getch();cleardevice(); mainmenu(); }

if(m1==1){ setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(20,20,600,475);
rectangle(30,30,590,465) ;
setcolor(LIGHTRED);
settextstyle(3,0,1);
setcolor(LIGHTRED);
outtextxy(160,160,"PLESE CHOOSE THE SEVICE !");
outtextxy(120,200," AUGMENT THE INFORMATION OF THE BUILDING (B)!");
outtextxy(120,240," AUGMENT THE INFORMATION OF THE BUILDING (P) !");
switch(getch()){case'B':{cleardevice();buildingmap();cleardevice();};break;
case 'P':{cleardevice();pathmap();cleardevice();};break;
default: cleardevice();mainmenu();}
}
if(m1==2){
interface();
getch();}
if(m1==3){exit(0); }
}

}

}
void con()
{setcolor(YELLOW); outtextxy(160,160+m1*40,str2[m1]); setcolor(CYAN); outtextxy(160,160+n1*40,str2[n1]); }
void interface()
{ int i,j;
char str[10];
setbkcolor(BLACK);
setcolor(LIGHTGRAY);
rectangle(20,20,600,100);
rectangle (20,20,600,470);
rectangle (20,100,450,470) ;
rectangle(20,350,450,470);
rectangle(20,100,300,350);
settextstyle(3,0,3);
outtextxy(200,30,"WELCOME TO");
outtextxy(120,60,"NORTHEAST DIANLI UNIVERSITY!") ;
outtextxy(460,200,"FROM : ___");
outtextxy(485,250,"TO : ___");
settextstyle(2,0,5);
rectangle(475,315,535,335);
rectangle(475,365,535,385);
outtextxy(455,150,"(PLEASE INPUT!)");
outtextxy(175,360,"THE RESULT !");
outtextxy(500,320,"F");
outtextxy(500,370,"Q");
outtextxy(480,400,"Input");
outtextxy(460,420, "the number 1-->6");
setcolor(RED);
drawbuilding();
drawedge();
i=0;
while(i<'1'||i>'6') i=getch();
sprintf(str,"%c",i);
outtextxy(560,205,str);
while(j<'1'||j>'6') j=getch();
sprintf(str,"%c",j);
outtextxy(560,255,str);
i=i-48;j=j-48;
floyd(g,n,dd[n+1][n+1],pp[n+1][n+1]);
display (i,j,pp[n+1][n+1], dd[n+1][n+1]);
drawpath( );
}
void interface1()
{
setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(20,20,600,475);
rectangle(30,30,590,465) ;
settextstyle(4,0,4);
setcolor(LIGHTRED);

settextstyle(3,0,1);
setcolor(LIGHTRED);
outtextxy(160,160,str3[0]);
outtextxy(160,200,str3[1]);
outtextxy(210,240,str3[2]);
outtextxy(210,280,str3[3]);

}

void again()
{int i; if(start==0) {for (i=0;i<300;i++) delay(1000);}
}

void drawbuilding()
{ int i,a;char str[10];
FILE *fp;
if ((fp=fopen("map.dat","r"))==NULL)
{
printf("Can not open the file of map.dat.\n");
exit(0);
}

for(i=0;i<n;i++)
{fread(&bd[i],sizeof(struct viewpoint),1,fp); point[i].number=bd[i].number; point[i].x_1=bd[i].x; point[i].y_1=bd[i].y; setcolor(RED); a=bd[i].number; sprintf(str,"%d",a); again(); circle(bd[i].x,bd[i].y,8); setcolor(LIGHTGRAY); outtextxy(bd[i].x-2,bd[i].y-5,str); outtextxy(310,i*30+120,str); outtextxy(325,i*30+120,":"); outtextxy(340,i*30+120,bd[i].inf); again(); }

fclose(fp);

}

void drawedge()
{ FILE *fp;char str[10];
int i,j,x1,x2,y1,y2,a;
if((fp=fopen("pmap.dat","r"))==NULL)
{ printf ("can't open the file\n");
exit(0);
}

for (i=0;i<=n;i++)
{for (j=0;j<=n;j++) g.edge[i][j]=maxdist;}
for(j=1;j<=n;j++)
g.edge[j][j]=0;
while(!feof(fp))
{ fread(&p[i],sizeof(struct path),1,fp);
if(p[i].V1!=0)
{
{g.edge[p[i].V1][p[i].V2]=p[i].length; g.edge[p[i].V2][p[i].V1]=p[i].length; }
setcolor(LIGHTBLUE);
for(j=0;j<n;j++)
{if(p[i].V1-point[j].number==0) {x1=point[j].x_1; y1=point[j].y_1; }
}

for(j=0;j<n;j++)
{if(p[i].V2==point[j].number) { x2=point[j].x_1; y2=point[j].y_1; }

}
line(x1,y1,x2,y2);
setcolor(LIGHTGRAY);
a=p[i].length;
sprintf(str,"%d",a);
outtextxy((x1+x2)/2,(y1+y2)/2,str);
again();
}
}

fclose(fp);
start=1;
}

void floyd(graph g,int m,int dd[n+1][n+1],int pp[n+1][n+1])
{int i,j,k,w; for(i=0;i<=m;i++) {for(j=0;j<=m;j++) dd[i][j]=maxdist;}

for(i=0;i<=m;i++)
{for(j=0;j<=m;j++) pp[i][j]=0; }
for(i=1;i<=m;i++)
{ for(j=1;j<=m;j++)
{dd[i][j]=g.edge[i][j]; if(dd[i][j]<maxdist&dd[i][j]!=0) pp[i][j]=j; else pp[i][j]=-1; } }
for(k=1;k<=m;k++)
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
if(dd[i][j]>(dd[i][k]+dd[k][j]))
{
dd[i][j]=dd[i][k]+dd[k][j];
pp[i][j]=k;
pp[j][i]=k;
}
}
void display(int i,int j,int pp[n+1][n+1],int dd[n+1][n+1])
{
int pre,flag,k,w=40;int m=0;
int str[10];
pre=k=j;
do { pre=pp[i][pre];
if(pre!=k)
sprintf(str,"%d",k);
outtextxy(120+w,390,str);

outtextxy(130+w,390,"<--");
a[m]=k;
m=m+1;
w=w+40;
k=pre;
pre=pp[i][pre];
flag=pre;
}while(flag!=k) ;

sprintf(str,"%d",flag);
outtextxy(120+w,390,str);
a[m]=flag;
outtextxy(130+w,390,"<--");
sprintf(str,"%d",i);
outtextxy(160+w,390,str);
a[m+1]=i;
a[m+2]=NULL;

outtextxy(60,390,"THE WAY IS:");
outtextxy(60,420,"THE SHORTEST WAY IS :");
sprintf(str,"%d",dd[i][j]);
outtextxy(240,420,str);

}
void drawpath( )
{ int i,j,x1,x2,y1,y2;
char l;
setcolor(RED);
for(i=0;i<n;i++)
{if(a[i+1]!=NULL) { again(); for(j=0;j<n;j++) {if(a[i]-point[j].number==0) {x1=point[j].x_1; y1=point[j].y_1; }
}

for(j=0;j<n;j++)
{if(a[i+1]==point[j].number) { x2=point[j].x_1; y2=point[j].y_1; }

}
line(x1,y1,x2,y2);

}
}
i=0;
while(i!='Q'&i!='F'&i!='q'&i!='f') i=getch();
switch(i)
{ case 'Q': {cleardevice(); mainmenu();};break;
case 'q': {cleardevice(); mainmenu();};break;
case 'F': {cleardevice();interface();};break;
case 'f': {cleardevice();interface();};break;
}
}

void buildingmap( )
{ FILE *fp;
int i;
setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(100,40,450,475);
rectangle(110,50,440,465) ;

setcolor(LIGHTRED);
settextstyle(2,0,4);
setcolor(LIGHTRED); if((fp=fopen("ss1-map","ab"))==NULL)
{ printf ("can't open the file\n");
exit(0);
}
outtextxy(160,100,"Please input the information of the building! ");
for(i=0;i<n;i++)
{ outtextxy(160,100+20*(i+1),"<--input data:" );
scanf("%d,%d,%d,%s\n",&bd[i].x,&bd[i].y,&bd[i].number,bd[i].inf );
if(fwrite(&bd[i],sizeof(struct viewpoint),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if(getch()=='Q') {cleardevice();mainmenu();}
}
void pathmap()
{FILE *fp; int i; cleardevice(); setbkcolor(BLACK); rectangle(100,40,450,475); rectangle(110,50,440,465) ; setcolor(LIGHTRED); settextstyle(2,0,4); if((fp=fopen("pp1-map","ab"))==NULL) { printf ("can't open the file\n"); exit(0); }
fseek(fp,0L,2);
outtextxy(160,100,"Please input the information of the building! ");
for(i=0;i<(n*n/2);i++)
{ outtextxy(160,100+20*(i+1),"<--input data:" );
scanf("%d,%d,%d\n",&p[i].V1,&p[i].V2,&p[i].length );
if(fwrite(&p[i],sizeof(struct path),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if(getch()=='Q') {cleardevice();mainmenu();}
}

㈨ c语言最短路径问题。

#include <stdio.h>
#define N 7 /* 顶点数目 */
#define I 999 /* 表示无穷大 */

int graph[N][N] = { /* 图的邻接矩阵 */
{I, 4, 5, 8, I, I, I},
{I, I, I, 6, 6, I, I},
{I, I, I, 5, I, 7, I},
{I, I, I, I, 8, 9, 9},
{I, I, I, I, I, I, 5},
{I, I, I, I, I, I, 4},
{I, I, I, I, I, I, I}
};
int List[N]; /* 存放拓扑序列 */

int TopologicalOrder(); /* 拓扑排序函数 */

void main() /* 主函数 */
{
int i, j, k, l;
int ee[N], el[N]; /* 最长最短距离 */
int path_e[N][N], path_l[N][N], n_e[N], n_l[N]; /* 记录路径数据 */

/* 初始化数据 */
for (i = 0; i < N; i++) {
n_e[i] = 0; /* 到 i 的最短路线的结点数 */
n_l[i] = 0; /* 到 i 的最长路线的结点数 */
ee[i] = I;
el[i] = 0;
}
ee[0] = el[0] = 0; /* 初始化头结点 */
path_e[0][0] = 0;
path_l[0][0] = 0;
n_e[0] = 1;
n_l[0] = 1;

/* 拓扑排序 */
if (!TopologicalOrder())
return;

/* 对于拓扑序列,运用动态规划步步算出最长路线与最短路线 */
for (i = 0; i < N; i++) {

/* 提取拓扑序列的元素 */
k = List[i];
/* 更新它所指向顶点的所有数据 */
for (j = 0; j < N; j++) {

/* 寻找指向的顶点 */
if (graph[k][j] != I) {

/* 如果新路径更短 */
if (graph[k][j] + ee[k] < ee[j]) {

/* 更新最短路径长度 */
ee[j] = graph[k][j] + ee[k];
/* 更新最短路线 */
for (l = 0; l < n_e[k]; l++) {
path_e[j][l] = path_e[k][l];
}
path_e[j][l] = j;
n_e[j] = l + 1;
}

/* 如果新路径更长 */
if (graph[k][j] + el[k] > el[j]) {

/* 更新最长路径长度 */
el[j] = graph[k][j] + el[k];
/* 更新最长路线 */
for (l = 0; l < n_l[k]; l++) {
path_l[j][l] = path_l[k][l];
}
path_l[j][l] = j;
n_l[j] = l + 1;
}
}
}
}

/* 输出结果到屏幕 */
for (i = 0; i < N; i++) {
printf("shortest(%d): %2d Path: ", i + 1, ee[i]);
for (j = 0; j < n_e[i]; j++) {
printf("%d ", path_e[i][j] + 1);
}
printf("\n");
printf("longest (%d): %2d Path: ", i + 1, el[i]);
for (j = 0; j < n_l[i]; j++) {
printf("%d ", path_l[i][j] + 1);
}
printf("\n");
}
}

int TopologicalOrder()
{
int i, j, top, count;
int indegree[N], Stack[N];

top = 0; /* 栈顶标志 */
for (i = 0; i < N; i++) {
indegree[i] = 0; /* 初始化入度 */
for (j = 0; j < N; j++) {
if (graph[j][i] != I) { /* 如连通 */
indegree[i]++; /* 入度自增1 */
}
}
if (!indegree[i]){ /* 如入度为零 */
Stack[top++] = i; /* 入栈 */
}
}
count = 0; /* 输出顶点数 */
while (top != 0) {
i = Stack[--top];
List[count++] = i;
for (j = 0; j < N; j++) {
if (graph[i][j] != I) { /* 如连通 */
if (!(--indegree[j])) { /* 而且入度为零 */
Stack[top++] = j; /* 入栈 */
}
}
}/* for */
}/* while */

return (count < N) ? 0 : 1;
}

㈩ c语言编写请简单点。用带权邻接矩阵输入一幅无向图，使用两种不同的算法计算出最短路径长度并输出路径。

//Floyed 实现赋权无向图定点对间的最短路径，时间复杂度O(n^3)
1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
#include<stdio.h>
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf("输入图的顶点数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("输入边(%d,%d)的权值,若不存在输入10000:",i,j);
scanf("%d",&c[i][j]);
}
}
如果是有向图就删掉这里"//for(i=1;i<=n;i++)
//{
///////////////////////////////////////for(j=1;j<=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}"
for(i=1;i<=n;i++)
c[i][i]=0;//自己到自己的权值为0
for(i=1;i<=n;i++) //初始化路径
{
for(j=1;j<=n;j++)
parth[i][j]=0;
}
for(k=1;k<=n;k++)//k是中间节点，i是起点j是中点。其实就是枚举中间节点，来求i j 的最短路径
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000&&t2!=10000&&(t3==10000||t1+t2<t3)) //松弛覆盖原来的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//记录i j的中间点是k
}
}
}
while(1)//也可以用递归的形式输出parth
{
printf("输入2点:");
scanf("%d%d",&x,&y);
printf("最短距离为%d\n",c[x][y]);
printf("%d ",x);
re=y;
while(parth[x][y]!=0)
{
printf("%d ",parth[x][y]);
y=parth[x][y];
}
printf("%d\n",re);
}
return 0;
}

导航:首页 > 源码编译 > c算法最短路径

c算法最短路径

与c算法最短路径相关的资料