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 = 1i <= ni++)

{

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 = 1i <ni++)

{

int temp = maxint

int u = v

//加入具有最小代价的邻居节点到s子集

for (j = 1j <= nj++)

{

if ((!s[j]) &&(dist[j] <temp))

{

u = j

temp = dist[j]

}

}

s[u] = 1

//计算加入新的节点后，更新路径使得其产生代价如歼最短

for (j = 1j <= nj++)

{

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 = countj >= 1j--)

{

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 = 1i <= ni++)

{

cost[i]=(int *)malloc(sizeof(int)*(n+1))

}

//输入代价矩阵

for (j = 1j <= nj++)

{

for (t = 1t <= nt++)

{

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 = 1i <= 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)

}

}

}

开始，笑凳运行（或者直接按Win+R），输入notepad

将下面两行百分号之间的内容复困升陆制进去，再保存成dijkstra.m，注意保存路汪顷径（最好保存到Matlab的工作路径中）

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [d,DD]=dijkstra(D,s)

%Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路

%D为赋权邻接矩阵

%d为s到其它各点最短路径的长度

%DD记载了最短路径生成树

[m,n]=size(D)

d=inf.*ones(1,m)

d(1,s)=0

dd=zeros(1,m)

dd(1,s)=1

y=s

DD=zeros(m,m)

DD(y,y)=1

counter=1

while length(find(dd==1))<m

for i=1:m

if dd(i)==0

d(i)=min(d(i),d(y)+D(y,i))

end

end

ddd=inf

for i=1:m

if dd(i)==0&&d(i)<ddd

ddd=d(i)

end

end

yy=find(d==ddd)

counter=counter+1

DD(y,yy(1,1))=counter

DD(yy(1,1),y)=counter

y=yy(1,1)

dd(1,y)=1

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

然后在matlab命令窗口中，生成D和s

然后调用：[d,DD]=dijkstra(D,s)

上学期曾经编过

是 离散数学 的题目吧

想要的话你得等等

我现在五一放假在家

程序在学校的笔记本上呢

下周一回学校

到时可以给你找找

和你的要求完全吻合（大概是完全吻合吧）

你还是留个邮箱吧

实验三 计算两结点间长度为m的路的数目

一、实验目的

熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。

二、实验内容

从键盘输入图的邻接矩阵和一正整数m，计算结点两两之间长度为m的路的数目。考虑有向图和无向图。用C语言实现。

三、实验步骤

1.根据算法画出程序流程图

2.根据流程图写源程序

3.编译连接源程序得出结果

四、源唤肆程序和实验结果

源程序：

#define n 5

#include <stdio.h>

void main(void)

{

int A[n][n],An[n][n],An_1[n][n]

int i,j,k,l,m

for(i=0i<ni++)

{

for(j=0j<nj++)

scanf("%d",&A[i][j])

}

printf("\n")

scanf("%d",&m)

for(i=0i<ni++)

for(j=0j<nj++)

An_1[i][j]=A[i][j]

for(l=0l<(m-1)l++)

{

for(i=0i<ni++)

for(j=0j<nj++)

for(k=0k<nk++)

{

if(k==0)An[i][j]=An_1[i][k]*A[k][j]

else An[i][j]=An[i][j]+(An_1[i][k]*A[k][j])

}

for(i=0i<ni++)

for(j=0j<nj++)

An_1[i][j]=An[i][j]

}

printf("An\n")

for(i=0i<ni++)

{

for(j=0j<nj++)

printf("%d ",An[i][j])

printf("\n"源丛)

}

}

实验结果：

0 1 0 0 0

1 0 1 0 0

0 1 0 0 0

0 0 0 0 1

0 0 0 1 0

4

An

2 0 2 0 0

0 4 0 0 0

2 0 2 0 0

0 0 0 1 0

0 0 0 0 1

Press any key to continue

不好意思 错了 没权值矩阵 不好意思

分给上边的那位吧和裂轿

不好意思 又找到了 东西有点乱。。。。

#define n 5

#include <stdio.h>

void main(void)

{

int bijiao(int a,int b,int c[n])

int linjie[n][n]={0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0}//邻接矩阵

int quanzhi[n][n]={0,1,0,3,2,1,0,2,2,1,0,2,0,2,0,3,2,2,0,3,2,1,0,3,0}//权值矩阵

int yi[n]={100,100,100,100,100},shengchengshu[n][n],shengchengshu2[n][n]

int i,j,k,temp1,temp2,temp3,he=0,buchonghe

for(i=0i<ni++)

for(j=0j<nj++)

shengchengshu[i][j]=0

temp1=100

for(i=0i<ni++)

for(j=ij<nj++)

if((quanzhi[i][j]<temp1)&&(quanzhi[i][j]!=0))

{

temp1=quanzhi[i][j]

yi[0]=i

yi[1]=j

}

shengchengshu[yi[0]][yi[1]]=1

printf("temp1=%d\n",temp1)

he=he+temp1

for(k=0k<(n-2)k++)

{

temp2=100

for(i=0i<(k+2)i++)

for(j=0j<nj++)

if(linjie[yi[i]][j]==1)

if(buchonghe=bijiao(k,j,yi))

if((quanzhi[yi[i]][j]<temp2)&&(quanzhi[yi[i]][j]!=0))

{

temp2=quanzhi[yi[i]][j]

yi[k+2]=j

temp3=yi[i]

}

printf("temp2=%d\n",temp2)

shengchengshu[temp3][yi[k+2]]=1

he=he+temp2

}

for(i=0i<ni++)

for(j=0j<nj++)

shengchengshu2[j][i]=shengchengshu[i][j]

for(i=0i<ni++)

for(j=0j<nj++)

shengchengshu[i][j]=shengchengshu[i][j]||shengchengshu2[i][j]

printf("he=%d\n",he)

for(i=0i<ni++)

printf("%d",yi[i])

printf("\n")

for(i=0i<ni++)

{

for(j=0j<nj++)

printf("%d ",shengchengshu[i][j])

printf("\n")

}

}

int bijiao(int k,int j,int yi[n])

{

int i

int buchonghe

for(i=0i<(k+2)i++)

{

if(i==0)buchonghe=(j!=yi[i])

else buchonghe=(buchonghe&&(j!=yi[i]))

}

return buchonghe

}

和你的要求一模一样 用C语言实现的 就是当时为了调试没有输入

你自己把那两个矩阵改成输入就可以了

基本上所有变量都是用汉语拼音的 你应该可以看懂

我相信你的智商 嘿嘿 给分吧

---