怎样用DIJKSTRA算法设计最短路径
以下................
输入时，将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;
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex;
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex;
char path;
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“,#);
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=’v’;
poin-》vertex=’0’+i+1;
poin-》vertex=’\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=’v’;
lin-》vertex=’0’+temp;
lin-》vertex=’\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=’v’;
p-》vertex=’0’+i+1;
p-》vertex=’\0’;
p-》cost=0;
p-》Known=0;
}
else
{
p-》vertex=’v’;
p-》vertex=’0’+i+1;
p-》vertex=’\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==now-》vertex)
break;
else
result=result-》next;
}
linna=now-》work-》next;
while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
{
temp=linna-》vertex;
searc=tabhead-》next;
while(searc!=NULL)
{
if(searc-》vertex==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=’v’;
searc-》path=now-》vertex;
searc-》path=’\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-’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-’0’)!=start&&p!=NULL)
{
while(temp-》vertex!=p-》path&&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语言算n的阶乘的递归算法
思路：递归求阶乘函数，如果输入的参数等于1则返回1，否则返回n乘以该函数下次递归。
参考代码：
#include《stdio.h》
int fun(int n)
{
if(n==1||n==0) return 1;//如果参数是0或者1返回1
return n*fun(n-1);//否则返回n和下次递归的积
}
int main()
{
int n;
scanf(“%d“,&n);
printf(“%d\n“,fun(n));
return 0;
}
/*
5
120
*/
java中排序算法代码
package temp;
import sun.misc.Sort;
/**
* @author zengjl
* @version 1.0
* @since 2007-08-22
* @Des java几种基本排序方法
*/
/**
* SortUtil:排序方法
* 关于对排序方法的选择：这告诉我们，什么时候用什么排序最好。当人们渴望先知道排在前面的是谁时，
* 我们用选择排序；当我们不断拿到新的数并想保持已有的数始终有序时，我们用插入排序；当给出的数
* 列已经比较有序，只需要小幅度的调整一下时，我们用冒泡排序。
*/
public class SortUtil extends Sort {
/**
* 插入排序法
* @param data
* @Des 插入排序(Insertion Sort)是，每次从数列中取一个还没有取出过的数，并按照大小关系插入到已经取出的数中使得已经取出的数仍然有序。
*/
public int insertSort(int data) {
1/11页
int temp;
for (int i = 1; i 《 data.length; i++) {
for (int j = i; (j 》 0) && (data[j] 《 data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
return data;
}
/**
* 冒泡排序法
* @param data
* @return
* @Des 冒泡排序(Bubble Sort)分为若干趟进行，每一趟排序从前往后比较每两个相邻的元素的大小（因此一趟排序要比较n-1对位置相邻的数）并在
* 每次发现前面的那个数比紧接它后的数大时交换位置；进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作（最坏情况下要跑n-1趟，
* 这种情况在最小的数位于给定数列的最后面时发生）。事实上，在第一趟冒泡结束后，最后面那个数肯定是最大的了，于是第二次只需要对前面n-1
* 个数排序，这又将把这n-1个数中最小的数放到整个数列的倒数第二个位置。这样下去，冒泡排序第i趟结束后后面i个数都已经到位了，第i+1趟实
* 际上只考虑前n-i个数（需要的比较次数比前面所说的n-1要小）。这相当于用数学归纳法证明了冒泡排序的正确性
-最短路径
