c语言顶点到其他点的最短距离

① c语言，最短路问题，求解！

给你matlab的程序行不？呵呵 这个只要看懂算法就可以自己来的
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t))
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100

② 某一顶点到其他各点的最短路径算法实现

这个
http://www.sfcode.cn/soft/001973243.htm
或者这个
输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示
当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点
比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径
Dijkstra算法的完整实现版本，算法的源代码
/* Dijkstra.c

Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
char vertex[3];
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex[3];
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex[3];
char path[3];
struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
int i,j,num,temp,val;
char c;
struct Point *poinpre,*poinhead,*poin;
struct Link *linpre,*linhead,*lin;
struct Table *tabhead;
poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
poin->next=NULL;
poin->work=NULL;
restart:
printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");
printf("Please input the number of points:\n");
scanf("%d",&num);
if(num>maxver||num<1||num%1!=0)
{
printf("\nNumber of points exception!");
goto restart;
}
for(i=0;i<num;i++)
{
printf("Please input the points next to point %d,end with 0:\n",i+1);
poin=(struct Point *)malloc(sizeof(struct Point));
poinpre->next=poin;
poin->vertex[0]='v';
poin->vertex[1]='0'+i+1;
poin->vertex[2]='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;j<num-1;j++)
{
printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
scanf("%d",&temp);
if(temp==0)
{
lin->next=NULL;
break;
}
else
{
lin=(struct Link *)malloc(sizeof(struct Link));
linpre->next=lin;
lin->vertex[0]='v';
lin->vertex[1]='0'+temp;
lin->vertex[2]='\0';
printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
scanf("%d",&val);
lin->value=val;
linpre=linpre->next;
lin->next=NULL;
}
}
poinpre=poinpre->next;
poin->next=NULL;
}
printf("Please enter the vertex where Dijkstra algorithm starts:\n");
scanf("%d",&temp);
tabhead=CreateTable(temp,num);
Dijkstra(poinhead,tabhead);
PrintTable(temp,tabhead);
return OK;
}
struct Table * CreateTable(int vertex,int total)
{
struct Table *head,*pre,*p;
int i;
head=pre=p=(struct Table *)malloc(sizeof(struct Table));
p->next=NULL;
for(i=0;i<total;i++)
{
p=(struct Table *)malloc(sizeof(struct Table));
pre->next=p;
if(i+1==vertex)
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=0;
p->Known=0;
}
else
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=maxium;
p->Known=0;
}
p->next=NULL;
pre=pre->next;
}
return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
int costs;
char temp;
struct Point *poinhead=p1,*now;
struct Link *linna;
struct Table *tabhead=p2,*searc,*result;
while(1)
{
now=FindSmallest(tabhead,poinhead);
if(now==NULL)
break;
result=p2;
result=result->next;
while(result!=NULL)
{
if(result->vertex[1]==now->vertex[1])
break;
else
result=result->next;
}
linna=now->work->next;
while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
{
temp=linna->vertex[1];
searc=tabhead->next;
while(searc!=NULL)
{
if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/
{
if((result->cost+linna->value)<searc->cost)
{
searc->cost=result->cost+linna->value;/*set the new value*/
searc->path[0]='v';
searc->path[1]=now->vertex[1];
searc->path[2]='\0';
}
break;
}
else
searc=searc->next;
}
linna=linna->next;
}
}
return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
struct Point *result;
struct Table *temp;
int min=maxium,status=0;
head=head->next;
poinhead=poinhead->next;
while(head!=NULL)
{
if(!head->Known&&head->cost<min)
{
min=head->cost;
result=poinhead;
temp=head;
status=1;
}
head=head->next;
poinhead=poinhead->next;
}
if(status)
{
temp->Known=1;
return result;
}
else
return NULL;
}
int PrintTable(int start,struct Table *head)
{
struct Table *begin=head;
head=head->next;
while(head!=NULL)
{
if((head->vertex[1]-'0')!=start)
PrintPath(start,head,begin);
head=head->next;
}
return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
struct Table *temp=begin->next,*p,*t;
p=head;
t=begin;
if((p->vertex[1]-'0')!=start&&p!=NULL)
{
while(temp->vertex[1]!=p->path[1]&&temp!=NULL)
temp=temp->next;
PrintPath(start,temp,t);
printf("%s",p->vertex);
}
else
if(p!=NULL)
printf("\n%s",p->vertex);
return OK;
}

③ 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; v<G.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; w<G.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; i<G.vexnum; ++i) { // 其余G.vexnum-1个顶点
min = INFINITY; // 当前所知离v0顶点的最近距离
for (w=0; w<G.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; w<G.vexnum; ++w) // 更新当前最短路径及距离
if (!final[w] && (min+G.arcs[v][w].adj<D[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ

⑤ 求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语言 如何求一点，使其到平面上其他已知点的距离和最小

能具体点吗？
如果点少，或许可以用数学几何方法求
如果点多，估计就只能循环求近似点了

min=(x,y)到到其他点的距离和 （x，y可随意，一般取x=最小值，y=最小值）
for(x=最小值;x≤最大值;x增加)
for(y=最小值;y≤最大值;y增加)
if(点(x,y)到其他点的距离和 < min)
记录下(x,y);
这种方法只能求一个近似点，精确度取决于你设置的x、y的增加速率

⑦ 要求：要能输出图形的最短路径设计，用C语言编写，高手进！！！

这个是我以前参加省赛的时候写的,一直保存着的,应该是你这个问题的答案,语法上没有问题,因为以前我跑过的,这个是C++程序,不过C和C++在基础语法上没有任何区别的,在这里拿出来跟你分享,希望能得到你的分哦!呵呵!

/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图，有一个特异的顶点s称为缘。
单源最短路径问题，或者称为最短路径问题，是要确定从s到V中没一个其他
顶点的距离，这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给了c++下的源代码！
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;}
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}

/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
*****************************/

⑧ 数据结构求最短路径

用Dijkstra算法求从V1顶点到其他各顶点的最短距离和最短路径的C语言程序如下

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define N 6 // 顶点数

#define INF 32767

int adj_arr[N][N] = {{INF, 2, 3, INF, INF, INF},

{INF, INF, INF, 5, INF, INF},

{INF, INF, INF, 3, 10, INF},

{INF, INF, INF, INF, INF, 4},

{INF, INF, INF, INF, INF, INF},

{INF, INF, INF, INF, 2, INF}}; // 用一个全局二维数组存储带权有向图的邻接矩阵

void shortest_path(int start, int end);

void print_shortest_path(int* distance,int* path,int* used,int start,int end);

int main(){

int i;

char s1[3];

for(i=1;i<6;i++){

shortest_path(0, i);

}

return 0;

}

void shortest_path(int start, int end){ // 基于Dijkstra算法的最短路径函数

int distance[N]; // 用于存放起始点到其余各点的最短距离

int path[N]; // 用于存放起始点到其余各点最短路径的前一个顶点

int used[N] = { 0 }; // 用于标记该顶点是否已经找到最短路径

int i, j, min_node, min_dis, pass_flag = 0;

for(i = 0; i < N; i++){

distance[i] = adj_arr[start][i]; // 初始化距离数组

if(adj_arr[start][i] < INF){

path[i] = start; // 初始化路径数组

}else{

path[i] = -1;

}

}

used[start] = 1;

path[start] = start;

for(i = 0; i < N; i++){

min_dis = INF;

for(j = 0; j < N; j++){

if(used[j] == 0 && distance[j] < min_dis){

min_node = j;

min_dis = distance[j];

pass_flag++; // 标记是否存在通路

}

}

if(pass_flag != 0){

used[min_node] = 1;

for(j = 0; j < N; j++){

if(used[j] == 0){

if(adj_arr[min_node][j] < INF && distance[min_node] + adj_arr[min_node][j] < distance[j]){

distance[j] = distance[min_node] + adj_arr[min_node][j];

path[j] = min_node;

}

}

}

}else{

printf("没有通路! ");

return;

}

}

print_shortest_path(distance, path, used, start, end);

return;

}

void print_shortest_path(int* distance,int* path,int* used,int start,int end){ // 输出最短距离并打印最短路径

int i = 0, pre, inverse_path[N];

char s1[3],s2[3];

sprintf(s1, "V%d", (start+1));

sprintf(s2, "V%d", (end+1));

printf("从%s顶点到%s顶点的最短距离: %d ", s1, s2, distance[end]);

inverse_path[i] = end;

pre = path[end];

if(pre == -1){

printf("没有通路! ");

}else{

while(pre != start){

inverse_path[++i] = pre;

pre = path[pre];

}

inverse_path[++i] = start;

printf("从%s顶点到%s顶点的最短路径: ", s1, s2);

for(; i > 0; i--){

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s -> ", s1);

}

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s ", s1);

}

return;

}

⑨ 用c语言实现寻找最短距离的问题，照片是个例子，问题就是从x城市到y城市，如何给出最短距离的路线，这

单源最短路径问题，用Dijkstra算法求解。图的存储结构，有邻接矩阵和邻接表两种，邻接矩阵占用空间大，但是使用方便。这里就说一下邻接矩阵：

structGraph{
intmatrix[N][N];
inte;
};

N表示顶点数，就这幅图而言是5，e表示边数。matrix存储了顶点之间的距离，比如matrix[0][1]表示顶点0到顶点1之间的距离。matrix[n][n]表示一个顶点到它自己的距离，这个应当设为0。另外，若两个顶点之间没有边，应该用一个值（可以是负数）来标识它，这两项操作，应该在图的初始化时进行。

创建图之后，首先要输入边数，然后输入每条边的起点、终点和长度，来给数组matrix赋值。

然后就是使用算法了。

参考：http://www.cnblogs.com/dolphin0520/archive/2011/08/26/2155202.html