c语言最短路径问题。

#include <stdioh>

#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;

}

你的代码我自己重新写了一遍,字母换了但字母顺序没有换

你的问题在于出现了重复累加的情况，举例：

显而易见3条路，原代码计算结果为5，因为(k1,k2,k)在(1,7,5),(1,5,2),(1,5,3),(1,7,6),(1,6,4)的时候各增加了一次可以看出多增加了两次(因为1257和1467这条两路在第二轮判断时各多加了一次),实际上每次处理过循环之后,都会多加一次,因此我加入判断变量k0,只要循环内经过递归,那么结束时就会减一(如k1=1,k2=5时,实际上此时已经加过一次,在k=2,3时又加了两次,此时就需要减掉一次)

感谢题主的思路,手头在做介数中心性,之前一直在考虑生成所有最短路径的矩阵,但计算规模巨大,远不如这种方法简单

function n=fun2(k1,k2,G,D)

%求最短路径数目

%k1表示第一个点,k2表示第二个点,D表示距离矩阵

  num=size(G,1);

  n=0;

  k0=false;

  for k = 1:num

      if G(k,k2)&&D(k1,k2)==D(k1,k)+D(k,k2)%如果第k个点直接连通到k2且为k1,k2必经之点,则进入递归

          n = n + fun2(k1,k,G,D);

          k0=true;                         %如果循环内出现了递归则记为true

      end

  end

  if k0,n=n-1;end  %排除重复增加

  n=n+1;

end

运行:

G=[false,true,true,true,false,false,false;true,false,false,false,true,false,false;true,false,false,false,true,false,false;true,false,false,false,false,true,false;false,true,true,false,false,false,true;false,false,false,true,false,false,true;false,false,false,false,true,true,false];

k1=1;k2=7;

D=[NaN,1,1,1,2,2,3;1,NaN,2,2,1,3,2;1,2,NaN,2,1,3,2;1,2,2,NaN,3,1,2;2,1,1,3,NaN,2,1;2,3,3,1,2,NaN,1;3,2,2,2,1,1,NaN];

n=fun2(k1,k2,G,D);

以前搞建模在网上下到的代码，不是自己编的，但经过试验可以用，分享了：

function len=dijkstra(Input)

%最短路Dijkstra算法,同时给出路径，input为图矩阵

row=size(Input,1);

%赋初值

% s_path=1;

distance=infones(1,row);

distance(1)=0;

% flag(1)=1;

temp=1;

%求起点到各点的最短路的权

% s_path=ones(1,3);

while length(s_path)<row

pos=find(Input(temp, : )~=inf);

n=length(pos);

flag=ones(1,n);

for i=1:n

if (isempty(find(s_path==pos(i),1)))&&(distance(pos(i))>

(distance(temp)+Input(temp,pos(i))))

distance(pos(i))=distance(temp)+Input(temp,pos(i));

flag(pos(i))=temp;

end

end

k=inf;

for i=1:row

if (isempty(find(s_path==i,1)))&&(k>distance(i))

k=distance(i);

temp_2=i;

end

end

s_path=[s_path,temp_2];

temp=temp_2;

end

%用追溯法得到起点到各点的最短路的路线

len=zeros(1,row);

for endpoint=1:row

path=0; %初始化

path(1)=endpoint;

i=1;

while path(i)~=1

path(i+1)=flag(path(i));

i=i+1;

end

path(i)=1;

path=path(end:-1:1); %最短路径

short_distance=distance(endpoint); %最短路径权

len(endpoint)=short_distance; %起点到各点的最短距离

pathall=path; %总路径矩阵

end

len=len(25:end);

%{

disp('起点到各点的最短路径：');

celldisp(pathall);

%设法只画出最短路径

em=find(w==inf);

w(em)=0;

h = view(biograph(w,[],'ShowWeights','on'));

%}

邮箱给你发了个资料，多年前搞的，估计是忘了，也许这个函数有点问题，你按资料里的做吧

给出定点x0到u的最短距离在网络图之中，程序如下：clc

clear

%问题：对于无向图实现最短距离

%初始值

%Diikstra算法应用到网络中的最短距离

%求解出父亲点、最短路轻

%创建时间：20201018

w=10111inf infinf inf；%创建邻接矩阵

10 inf 11inf inf inf;

Tinf 0 1 inf inf Tinf:

1110111inf;

inf 1inf 10 1inf 1:

inf inf inf 110 11;

inf inf 11inf 101:

inf inf inf inf 11101;

n=size(w1);

w1=w(1:):

fori=tn

（i)=wT();%贼初值]

(v),Ku0)=0,Ku1)=2,Ku2)=1,Ku3)=81(u4)=in

f…

z（)=1;%这里所求的z（i)-1就是父亲点的意思

end

s-[1;

s(1)=1;%1代表U0

u=5(1;%这里对于我们的u的初始值选取

K=1;

%进行循环更新Kv)、z(v)

whilekcn%此处相当于让其初始值不变往下走

%更新(v)、z(v]

fori=tn

for j=Tk

if i"=s(j)

if 1Dak)+wui

Ki)=ku)+w(u,D);

zG)=u;

end

end

end

end

%第n次更新

11=1;%将更新后的|赋值给1目

for i=tn

for j=Tk

ifi”=s（j)%点集出列，不能选择

K）=lKi)；%边权不改变

elee

)=inf；%无关联的情况下当前点与具余点的

边权为元穷

end

end

end

lv=inf；%边权赋予给无穷

fori=1n %循环vO到v7寻找vO到v7的最短路

ifj)ly%如果边权点小于无穷，则lv返回i）

的值

lv=Ik);

V=i%顶点集更新，并且赋予给

end

end

lv；%输出边权

v;%输出顶点集

s(k+1)=v；%出列点

k=k+1;

u=s(k);

end

――

Z

输出结果：

1=

01112223

Z=

11112435

其中代表的是最短路径距离，z表示的是最短路径走向。从上述结果可知，路径为，v1--v2-v5-v8;其最短距离为1+2+3=6；所以得知该网络图的最短路距离径为6。对于Dijkstra算法得理解父亲点与距离权重，这是理解算法原理的基础！此代码的好处在于，你根据自己的问题，相应的把邻接矩阵改了就可以用！

第一步：首先必须在ArcCatalog中新建网络数据集，在网络图层点右键，选择新建网络数据集，如图所示，一路默认点击。如果你熟悉，修改其中的参数也可以。

{GZK09A)VRT5}06@~YCG)MX

第二步：在ArcMap中新增网络分析层保存为MXD文档，注意的是需要安装扩展模块，如果没有，可以在安装光盘中查找。

第三步：最后在ArcCatalog或者ArcGIS Server Manager中发布服务时发布，注意的是要选择网络分析服务。也就是NAServer。

下面的工作就是在程序中来编写如何来获取最短路径了，分成了两种方式：

第一种方式为客户端在地图控件上获取起始点，系统利用Ajax技术将起点与终点的屏幕坐标发送回GIS服务器，并通过服务器处理获取最短路径，以>

function [path, totalCost, farthestPreviousHop, farthestNextHop] = dijkstra(n, netCostMatrix, s, d, farthestPreviousHop, farthestNextHop)

% path: the list of nodes in the path from source to destination;

% totalCost: the total cost of the path;

% farthestNode: the farthest node to reach for each node after performing

% the routing;

% n: the number of nodes in the network;

% s: source node index;

% d: destination node index;

% clear;

% noOfNodes = 50;

% rand('state', 0);

% figure(1);

% clf;

% hold on;

% L = 1000;

% R = 200; % maximum range;

% netXloc = rand(1,noOfNodes)L;

% netYloc = rand(1,noOfNodes)L;

% for i = 1:noOfNodes

% plot(netXloc(i), netYloc(i), '');

% text(netXloc(i), netYloc(i), num2str(i));

% for j = 1:noOfNodes

% distance = sqrt((netXloc(i) - netXloc(j))^2 + (netYloc(i) - netYloc(j))^2);

% if distance = R

% matrix(i, j) = 1; % there is a link;

% line([netXloc(i) netXloc(j)], [netYloc(i) netYloc(j)], 'LineStyle', ':');

% else

% matrix(i, j) = inf;

% end;

% end;

% end;

%

%

% activeNodes = [];

% for i = 1:noOfNodes,

% % initialize the farthest node to be itself;

% farthestPreviousHop(i) = i; % used to compute the RTS/CTS range;

% farthestNextHop(i) = i;

% end;

%

% [path, totalCost, farthestPreviousHop, farthestNextHop] = dijkstra(noOfNodes, matrix, 1, 15, farthestPreviousHop, farthestNextHop);

% path

% totalCost

% if length(path) ~= 0

% for i = 1:(length(path)-1)

% line([netXloc(path(i)) netXloc(path(i+1))], [netYloc(path(i)) netYloc(path(i+1))], 'Color','r','LineWidth', 050, 'LineStyle', '-');

% end;

% end;

% hold off;

% return;

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

% all the nodes are un-visited;

visited(1:n) = 0;

distance(1:n) = inf; % it stores the shortest distance between each node and the source node;

parent(1:n) = 0;

distance(s) = 0;

for i = 1:(n-1),

temp = [];

for h = 1:n,

if visited(h) == 0 % in the tree;

temp=[temp distance(h)];

else

temp=[temp inf];

end

end;

[t, u] = min(temp); % it starts from node with the shortest distance to the source;

visited(u) = 1; % mark it as visited;

for v = 1:n, % for each neighbors of node u;

if ( ( netCostMatrix(u, v) + distance(u)) distance(v) )

distance(v) = distance(u) + netCostMatrix(u, v); % update the shortest distance when a shorter path is found;

parent(v) = u; % update its parent;

end;

end;

end;

path = [];

if parent(d) ~= 0 % if there is a path!

t = d;

path = [d];

while t ~= s

p = parent(t);

path = [p path];

if netCostMatrix(t, farthestPreviousHop(t)) netCostMatrix(t, p)

farthestPreviousHop(t) = p;

end;

if netCostMatrix(p, farthestNextHop(p)) netCostMatrix(p, t)

farthestNextHop(p) = t;

end;

t = p;

end;

end;

totalCost = distance(d);

return;

以上就是关于c语言最短路径问题。全部的内容，包括:c语言最短路径问题。、用matlab求两点间最短路径的数目，下面的程序有什么问题、matlab编程动态规划最短路径问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！