求单源最短路径算法和程序（程序不要用数据结构的）

你想输出路径吗？

记录一下每个点的直接前驱，然后反向查找

#include <stdioh>

const int maxdot=100;

int dist[maxdot];

int previous[maxdot]; //record the directly previous node

void ShortPaths(int v,int c[maxdot][maxdot],int n)

{

int i,j; bool s[maxdot];

int p[maxdot][maxdot];

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

{

dist[i]=c[v][i];

previous[i]=v;

s[i]=false;

}

dist[v]=0;s[v]=true;

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

{

int temp=10000;

int u=v;

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

{

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

{

u=j;

temp=dist[j];

}

}

s[u]=true;

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

{

if(!s[j]&&(c[u][j]<1000))

{

int newdist=dist[u]+c[u][j];

if(newdist<dist[j])

{

dist[j]=newdist;

previous[j]=u; //update the directly previous node

}

}

}

}

}

void find(int v,int u) // 'v' here must be identical with the 'v' in above function

{

//output the path in reverse order

while(u!=previous[u])

{

u=previous[u]; // retrieve the previous node

printf("%d\n",u);

}

}

var n,i,j,ans:integer;

 a:array[1100,1100]of integer;

begin

read(n);

for i:=1 to n do

for j:=1 to i do read(a[i,j]);

a[n]:=a[n];

for i:=n-1 downto 1 do

for j:=1 to i do

if a[i+1,j]<a[i+1,j+1] then a[i,j]:=a[i+1,j+1]+a[i,j]

                       else a[i,j]:=a[i+1,j]+a[i,j];

writeln(a[1,1]);

end

算法要求：

1 在一个无向连通图中求出两个给定点之间的所有路径；

2 在所得路径上不能含有环路或重复的点；

算法思想描述：

1 整理节点间的关系，为每个节点建立一个集合，该集合中保存所有与该节点直接相连的节点（不包括该节点自身）；

2 定义两点一个为起始节点，另一个为终点，求解两者之间的所有路径的问题可以被分解为如下所述的子问题：对每一 个与起始节点直接相连的节点，求解它到终点的所有路径（路径上不包括起始节点）得到一个路径集合，将这些路径集合相加就可以得到起始节点到终点的所有路径；依次类推就可以应用递归的思想，层层递归直到终点，若发现希望得到的一条路径，则转储并打印输出；若发现环路，或发现死路，则停止寻路并返回；

3 用栈保存当前已经寻到的路径（不是完整路径）上的节点，在每一次寻到完整路径时d出栈顶节点；而在遇到从栈顶节点无法继续向下寻路时也d出该栈顶节点，从而实现回溯。

实现代码

1Nodejava

[java] view plaincopy

import javautilArrayList;

/ 表示一个节点以及和这个节点相连的所有节点 /

public class Node

{

public String name = null;

public ArrayList<Node> relationNodes = new ArrayList<Node>();

public String getName() {

return name;

}

public void setName(String name) {

thisname = name;

}

public ArrayList<Node> getRelationNodes() {

return relationNodes;

}

public void setRelationNodes(ArrayList<Node> relationNodes) {

thisrelationNodes = relationNodes;

}

}

2testjava

[java] view plaincopy

import javautilArrayList;

import javautilIterator;

import javautilStack;

public class test {

/ 临时保存路径节点的栈 /

public static Stack<Node> stack = new Stack<Node>();

/ 存储路径的集合 /

public static ArrayList<Object[]> sers = new ArrayList<Object[]>();

/ 判断节点是否在栈中 /

public static boolean isNodeInStack(Node node)

{

Iterator<Node> it = stackiterator();

while (ithasNext()) {

Node node1 = (Node) itnext();

if (node == node1)

return true;

}

return false;

}

/ 此时栈中的节点组成一条所求路径，转储并打印输出 /

public static void showAndSavePath()

{

Object[] o = stacktoArray();

for (int i = 0; i < olength; i++) {

Node nNode = (Node) o[i];

if(i < (olength - 1))

Systemoutprint(nNodegetName() + "->");

else

Systemoutprint(nNodegetName());

}

sersadd(o); / 转储 /

Systemoutprintln("\n");

}

/

寻找路径的方法

cNode: 当前的起始节点currentNode

pNode: 当前起始节点的上一节点previousNode

sNode: 最初的起始节点startNode

eNode: 终点endNode

/

public static boolean getPaths(Node cNode, Node pNode, Node sNode, Node eNode) {

Node nNode = null;

/ 如果符合条件判断说明出现环路，不能再顺着该路径继续寻路，返回false /

if (cNode != null && pNode != null && cNode == pNode)

return false;

if (cNode != null) {

int i = 0;

/ 起始节点入栈 /

stackpush(cNode);

/ 如果该起始节点就是终点，说明找到一条路径 /

if (cNode == eNode)

{

/ 转储并打印输出该路径，返回true /

showAndSavePath();

return true;

}

/ 如果不是,继续寻路 /

else

{

/

从与当前起始节点cNode有连接关系的节点集中按顺序遍历得到一个节点

作为下一次递归寻路时的起始节点

/

nNode = cNodegetRelationNodes()get(i);

while (nNode != null) {

/

如果nNode是最初的起始节点或者nNode就是cNode的上一节点或者nNode已经在栈中 ，

说明产生环路 ，应重新在与当前起始节点有连接关系的节点集中寻找nNode

/

if (pNode != null

&& (nNode == sNode || nNode == pNode || isNodeInStack(nNode))) {

i++;

if (i >= cNodegetRelationNodes()size())

nNode = null;

else

nNode = cNodegetRelationNodes()get(i);

continue;

}

/ 以nNode为新的起始节点，当前起始节点cNode为上一节点，递归调用寻路方法 /

if (getPaths(nNode, cNode, sNode, eNode))/ 递归调用 /

{

/ 如果找到一条路径，则d出栈顶节点 /

stackpop();

}

/ 继续在与cNode有连接关系的节点集中测试nNode /

i++;

if (i >= cNodegetRelationNodes()size())

nNode = null;

else

nNode = cNodegetRelationNodes()get(i);

}

/

当遍历完所有与cNode有连接关系的节点后，

说明在以cNode为起始节点到终点的路径已经全部找到

/

stackpop();

return false;

}

} else

return false;

}

public static void main(String[] args) {

/ 定义节点关系 /

int nodeRalation[][] =

{

{1}, //0

{0,5,2,3},//1

{1,4}, //2

{1,4}, //3

{2,3,5}, //4

{1,4} //5

};

/ 定义节点数组 /

Node[] node = new Node[nodeRalationlength];

for(int i=0;i<nodeRalationlength;i++)

{

node[i] = new Node();

node[i]setName("node" + i);

}

/ 定义与节点相关联的节点集合 /

for(int i=0;i<nodeRalationlength;i++)

{

ArrayList<Node> List = new ArrayList<Node>();

for(int j=0;j<nodeRalation[i]length;j++)

{

Listadd(node[nodeRalation[i][j]]);

}

node[i]setRelationNodes(List);

List = null; //释放内存

}

/ 开始搜索所有路径 /

getPaths(node[0], null, node[0], node[4]);

}

}

输出：

node0->node1->node5->node4

node0->node1->node2->node4

node0->node1->node3->node4

你是大二的计算机学生，实在不清楚你是否学过“代数组合”，你这个问题用代数组合的方式处理是最方便的，算一下k个矩阵相乘即可——设矩阵A的第i行第j列的整数为从顶点i到顶点j的路径数（特别的，矩阵对角线全部设为零，反正你不要回路），那么A的k次方这个矩阵的第i行第j列整数就表示从顶点i到顶点j长度为k的路径数，这个不难证明的自己琢磨一下就好了，矩阵相乘的程序很简单的，你如果对代数组合或者这类图计算比较感兴趣，那就给你一本书吧，上传不了附件如果需要留个邮箱我发给你。

以上就是关于求单源最短路径算法和程序（程序不要用数据结构的）全部的内容，包括:求单源最短路径算法和程序（程序不要用数据结构的）、pascal题目：数字三角形。如图1，所示为一个数字三角形。请编写一个程序计算从顶到底的一条路径。、搜索无向图两点间所有路径，无向图可能比较复杂。等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！