本文目录一览：
- 1、怎么用c语言实现单源最短路径问题？要求是用Dijkstra算法，最好写出所有的代码 ，包括结构定义等等，对一
- 2、C语言最短路径
- 3、c语言数据结构 最短路径问题代码
- 4、c语言编程求矩阵的最大值，最小值及所在的位置
- 5、用dijkstra算法解决最短路径问题c语言代码实现时怎样将每一个路径的顶点次序依次输出出来？
- 6、c语言最短路径问题。
怎么用c语言实现单源最短路径问题？要求是用Dijkstra算法，最好写出所有的代码 ，包括结构定义等等，对一
C语言代码：//清华大学出版社光盘的代码
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D)
{ // 算法7.15
// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]
// 及其带权长度D[v]。
// 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。
// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; vG.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; wG.vexnum; ++w) P[v][w] = FALSE; // 设空路径
if (D[v] INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集
//--- 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 ---
for (i=1; iG.vexnum; ++i) { // 其余G.vexnum-1个顶点
min = INFINITY; // 当前所知离v0顶点的最近距离
for (w=0; wG.vexnum; ++w)
if (!final[w]) // w顶点在V-S中
if (D[w]min) { v = w; min = D[w]; } // w顶点离v0顶点更近
final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w=0; wG.vexnum; ++w) // 更新当前最短路径及距离
if (!final[w] (min+G.arcs[v][w].adjD[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;jG.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ
C语言最短路径
int main()
{
int G[100][100] = {};
//一个记录图的邻接矩阵
int a, b, w;
//输入一共有7条边, 5个点
int i, j, k;
for(i = 1;i = 5;i++)
for(j = 1;j = 5;j++)
G[i][j] = 9999999;
for(i = 1;i = 7;i++)
{
scanf("%d %d %d", a, b, w);//输入每条边的信息，a和b代表这条边的两个顶点w代表两个点的距离
G[a][b] = w;
G[b][a] = w;
}
for(k = 1;k = 5;k++)
for(i = 1;i = 5;i++)
for(j = 1;j = 5;j++)
if(G[i][j] G[i][k] + G[k][j])
G[i][j] = G[i][k] + G[k][j];
printf("%d", G[1][4]);//输出两点之间的最短路，这里的两个点是3和5
return 0;
}
G[i][j]代表i到j的距离，甲，乙，丙，丁，戊用1，2，3，4，5代替
如果你还不懂的话，就看一些关于图论的问题，这个最短路是图论中的一个经典题
c语言数据结构 最短路径问题代码
直接看代码：
#include stdlib.h
#define MAXVEX 10
typedef struct graph{
int n,e;//顶点数、边数
char vexs[MAXVEX];//顶点数组
int arcs[MAXVEX][MAXVEX];//邻接矩阵
int kind;//类型：0有向图；1无向图；2有向网；3无向网
} MGraph;
void PrintPath(MGraph G,int *p,int i){
if(p[i]=0){
PrintPath(G,p,p[i]);//先输出前驱顶点
}
printf("%c",G.vexs[i]);//输出本顶点
}
void Dijkstra(MGraph G, int v){
//用Dijkstra算法求有向网G中序号为v的顶点到
//其余各顶点的最短路径
int *s,*d,*p,i,j,k,min;
if(v0||v=G.n){//顶点编号参数错误
printf("Dijkstra parameter ERROR! v0 Or v=%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;iG.n;i++){ //初始化辅助数组，置0
s[i]=0;d[i]=G.arcs[v][i];
if(d[i]!=0)p[i]=v; //v是vi的直接前驱
else p[i]=-1; //-1表示无直接前驱
}
s[v]=1;d[v]=0; //确定源点自身的最短路径长度
printf("Dijkstra: (The shortest path from %c:)\n",G.vexs[v]);
for(i=0;iG.n-1;i++){
//确定v到其余n-1个顶点的最短路径
min=32767;k=-1;
for(j=0;jG.n;j++){
//找出路径长度最小的顶点k
if(!s[j]d[j]!=0d[j]min){
k=j; min=d[k];
}
}
if(k0){//有未能到达的顶点，把它们输出
for(j=0;jG.n;++j){
if(j==v)continue;
if(s[j]==0){
printf("%c-%c: No path.\n",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("\n");
for(j=0;jG.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语言编程求矩阵的最大值，最小值及所在的位置
#includestdio.h
int a[9][9]={{5,15,9,16,7,10,2,6,3,20}};
//最大值函数声明
int getmax(int *,int *);
//最小值函数声明
int getmin(int *,int *)
//主函数
void main(void)
{
int imax,jmax,imin,jmin;
printf("矩阵最大值为%d,位置为%d行，%d列；",getmax(imax,jmax),imax,jmax);
printf("最小值为%d，位置为%d行，%d列;",getmin(imin,jmin),imin,jmin);
printf("正对角线和为%d!",getlsum());
printf("反对角线和为%d!",getrsum());
}
//求最大值函数
int getmax(int * imax,int * jmax)
{
int max=0;
for(int i=0;i9;i++)
for(int j=0;j9;j++)
{
if(a[i][j]max)
{
*imax=i;
*jmax=j;
max=a[i][j];
}
}
return max;
}
//求最小值函数
int getmin(int * imin,int * jmin)
{
int min=65535;
for(int i=0;i9;i++)
for(int j=0;j9;j++)
{
if(a[i][j]min)
{
*imin=i;
*jmin=j;
min=a[i][j];
}
}
return min;
}
//求正对角线和函数
int getlsum()
{
int sum=0;
for(int i=0;i9;i++)
sum+=a[i][i];
return sum
}
//求反对角线和函数
int getrsum()
{
int sum=0;
for(int i=0;i9;i++)
sum+=a[i][9-i];
return sum;
}
程序写好了，放在一起的，公用一个主函数，如果不要显示哪个功能就把哪块干掉，如果这你都不会我就没办法了！！！
用dijkstra算法解决最短路径问题c语言代码实现时怎样将每一个路径的顶点次序依次输出出来？
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 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;
}
