怎样用DIJKSTRA算法设计最短路径?这是我们的作业,可我不太会做,想找高手帮忙设计出这个程序.有图,有数组,都是我自己弄的.请好心人与我联系295702184.先悬赏100,并补献全部积分,若成功还可有

怎样用DIJKSTRA算法设计最短路径?这是我们的作业,可我不太会做,想找高手帮忙设计出这个程序.有图,有数组,都是我自己弄的.请好心人与我联系295702184.先悬赏100,并补献全部积分,若成功还可有
怎样用DIJKSTRA算法设计最短路径?
这是我们的作业,可我不太会做,想找高手帮忙设计出这个程序.
有图,有数组,都是我自己弄的.
请好心人与我联系295702184.
先悬赏100,并补献全部积分,若成功还可有额外补助~
请高手速与我联系!
要C语言环境下的程序～
现在已有现成程序，只需做少许改动。

怎样用DIJKSTRA算法设计最短路径?这是我们的作业,可我不太会做,想找高手帮忙设计出这个程序.有图,有数组,都是我自己弄的.请好心人与我联系295702184.先悬赏100,并补献全部积分,若成功还可有
浠ヤ笅.
杈撳叆鏃?灏唖,t,x,y,z浜斾釜鐐规寜鐓?,2,3,4,5璧峰埆鍚?杈撳叆鏍煎紡鎸夌収涓嬪浘渚嬫墍绀裹br/>褰撴彁绀篜lease enter the vertex where Dijkstra algorithm starts:鏃惰緭鍏ョ畻娉曠殑璧峰?鐐更br/>姣斿?璁＄畻缁撴灉v1v4v2琛ㄧず浠庣偣1鍒扮偣2缁忚繃1,4,2涓烘渶鐭?矾寰凕br/>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||numvertex[0]='v';
poin->vertex[1]='0'+i+1;
poin->vertex[2]='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;jnext=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;inext=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)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->costcost;
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;
}

侥幸通过了CodeJam的外围赛，要在500进250的比赛中胜出，以目前的实力还不可能，虽然在topcoder上做了很多练习题，但感觉水平停留在Division II上，对于Division I基本上只能解出最低难度的。要想进一步提高，就不能靠单纯的练习了，需要继续学习新的知识，加强算法方面的基础。
TopCoder上经常有介绍算法的好文章，晚上看了Graph Theory的一篇教程，系统...

全部展开

侥幸通过了CodeJam的外围赛，要在500进250的比赛中胜出，以目前的实力还不可能，虽然在topcoder上做了很多练习题，但感觉水平停留在Division II上，对于Division I基本上只能解出最低难度的。要想进一步提高，就不能靠单纯的练习了，需要继续学习新的知识，加强算法方面的基础。
TopCoder上经常有介绍算法的好文章，晚上看了Graph Theory的一篇教程，系统的介绍了深度优先搜索和广度优先搜索的基本知识，在第三节里介绍了寻找图中最短路径的两种方法：Dijkstra（堆法）和Floyd Warshall法。
Dijkstra不知道该怎么发音，这种方法本质上是一个广度优先搜索的算法，通过使用priority queue使取值最小的节点始终位于队列的前端，从而达到O(m * log n)的时间复杂度，其中n为图的顶点数，m为图的边数。这个算法的基本结构为：
void dijkstra(node start) {
priorityqueue s;
s.push(start);
while (s.empty() == false) {
top = s.top();
s.pop();
//标记top为已访问//检查是否达到终止条件，如遍历所有节点//将top的所有邻居加入队列 }
}这种方法与普通的广度优先算法区别在于，它不需要遍历所有可能的情况便可以找出最短的一条路径。因为每次取出的都是当前已搜索路径中的最小值，如果已经到达目的地，那么其他可能到达的目的地的路径必然大于此。可以从KiloManX这道题的解法中对这个算法有更深入的理解。这个题目粗看起来应该用动态规划求解，实际上用Dijkstra法可以达到更高的效率。这个算法的一个C++实现如下所示，注意STL里的priority queue是把最大元素放在队首的。using namespace std;typedef struct node{??? int weapons;??? //also represent defeated bosses??? int shots;??? ??? //total shots needed??? node(int w, int s){weapons=w;shots=s;}??? friend bool operator ??? ??? if(n1.shots!=n2.shots) return n1.shots>n2.shots;??? //reverse sorting??? ??? if(n1.weapons!=n2.weapons) return n1.weapons>n2.weapons;??? ??? return false;??? }} node;class KiloManX{public:??? int leastShots(vector damageChart, vector bossHealth) ??? { ??? ??? int ans=-1;??? ??? int num=(int)damageChart.size();??? ??? vector visited(1??? ??? priorityqueue pq;
??? ??? pq.push(node(0,0));
??? ??? while(pq.empty()==false){
??? ??? ??? node top=pq.top();
??? ??? ??? pq.pop();
??? ??? ??? if(visited[top.weapons]) continue;
??? ??? ??? visited[top.weapons]=true;
??? ??? ??? if(top.weapons==((1??? ??? ??? for(int i=0;i??? ??? ??? ??? //if the boss has been defeated
??? ??? ??? ??? if((top.weapons>>i)&1) continue;
??? ??? ??? ??? int best=bossHealth[i];
??? ??? ??? ??? for(int j=0;j??? ??? ??? ??? ??? if(i==j) continue;
??? ??? ??? ??? ??? int shotsNeeded=bossHealth[i];
??? ??? ??? ??? ??? int damage=damageChart[j][i]-’0′;
??? ??? ??? ??? ??? if(((top.weapons>>j)&1)&&(damage!=0)){
??? ??? ??? ??? ??? ??? shotsNeeded=(bossHealth[i]-1)/damage+1;
??? ??? ??? ??? ??? }
??? ??? ??? ??? ??? best=min(best,shotsNeeded);
??? ??? ??? ??? }
??? ??? ??? ??? pq.push(node(top.weapons|(1??? ??? ??? }
??? ??? }
??? ??? return ans;
??? }
]]>

收起

贪心法_单源最短路径_Dijkstra
问题描述
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。
另外，还给定 V 中的一个项点，称为源。
现在我们要计算从源到所有其他各项点的最短路径长度。
这里的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
算法基本思想
Dijkstra算法是解单源最短路...

全部展开

贪心法_单源最短路径_Dijkstra
问题描述
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。
另外，还给定 V 中的一个项点，称为源。
现在我们要计算从源到所有其他各项点的最短路径长度。
这里的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
算法基本思想
Dijkstra算法是解单源最短路径问题的一个贪心算法。
其基本思想是，设置一个基点集合 S ，并不断地作贪心
选择来扩充这个集合。
一个项点属于集合 S 当且仅当从源到该项点的最短路
径长度已知。
初始时，S中仅含有源。设 u 是 G 的某一个项点，
我们把从源到 u 且中间只有经过 S 中项点的路称为
从源到 u 的特殊路径，并且数组 dist 来记录当前每个
项点所对应的最短特殊路径长度。
Dijkstra算法每次从 V-S 中取出具有最短特殊路径长度
的项点 u ，将 u 添加到 S 中，同时对数组 dist 作必要
的修改。
源程序:
////////////////////////////////////////////////////////////
// 程序员：HayMaN
// 功能：用 '贪心法' 解 '单源最短路径'
// 时间：18:58 2006-11-24
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
// Graph.h
#pragma once
#define maxPoint 100
class CGraph
{
public:
CGraph(void);
~CGraph(void);
bool SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size );
bool Dijkstra();
void Display();
int GetStartPoint();
double GetBestWay( int dest , int path[] , int &pathLen );
private:
//标志当前图是否已经求解
bool solved;
//当前图布局
double graph[maxPoint][maxPoint];
//地图大小
int size;
//起点
int startPoint;
//当前图的解
double dist[maxPoint];
int prev[maxPoint];
};
////////////////////////////////////////////////////////////
// Graph.cpp
#include 'StdAfx.h'
#include '.\graph.h'
CGraph::CGraph(void)
{
for( int i = 0 ; i < maxPoint ; i++ )
{
for( int j = 0 ; j < maxPoint ; j++ )
graph[i][j] = -1;
}
startPoint = -1;
size = -1;
//当前图还没有求解
solved = false;
}
CGraph::~CGraph(void)
{
}
//
//
bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )
{
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
graph[i][j] = g[i][j];
}
this->startPoint = startPoint;
this->size = size;
solved = false;
Dijkstra();
return true;
}
//
//
bool CGraph::Dijkstra()
{
bool s[maxPoint];
for( int j = 0 ; j < size ; j++ )
{
dist[j] = graph[startPoint][j];
s[j] = false;
//dist[i]<0，表示没有路径连接 结点startPoint 与 结点j
if( dist[j] < 0 )
prev[j] = 0;
else
prev[j] = startPoint;
}
//从起点出发
dist[startPoint] = 0;
s[startPoint] = true;
for( int i = 0 ; i < size ; i++ )
{
double temp;
int u = startPoint;
bool flag = false;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] )
{
//如果不是第一次比较，temp u，都已经赋值，则
if( flag )
{
if( dist[j] > 0 && dist[j] < temp )
{
u = j;
temp = dist[j];
}
}
else
{
u = j;
temp = dist[j];
flag = true;
}
}
}
s[u] = true;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] && graph[u][j] > 0 )
{
double newDist = dist[u] + graph[u][j];
if( dist[j] < 0 || newDist < dist[j] )
{
dist[j] = newDist;
prev[j] = u;
}
}
}
}
//标记当前问题已经解决
solved = true;
return true;
}
//
//
void CGraph::Display()
{
printf( '当前地图的邻接矩阵\n' );
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
{
printf( '%5.f' , graph[i][j] );
}
printf( '\n' );
}
}
//
//
double CGraph::GetBestWay( int dest , int path[] , int &pathLen )
{
int p = dest;
int theway[maxPoint];
int len = 0;
while( p != startPoint )
{
theway[len] = p;
p = prev[p];
len++;
}
theway[len] = startPoint;
len++;
for( int i = 0 , j = len - 1 ; i < len ; i++ , j-- )
path[i] = theway[j];
pathLen = len;
return dist[dest];
}
//
//
int CGraph::GetStartPoint()
{
return startPoint;
}
//
////////////////////////////////////////////////////////////
// Dijkstra.cpp : 定义控制台应用程序的入口点。
//
#include 'stdafx.h'
#include 'conio.h'
#include 'Graph.h'
int _tmain(int argc, _TCHAR* argv[])
{
double graph[][maxPoint] =
{
{ 1 , 10 , -1 , 30 , 100 } ,
{ -1 , 0 , 50 , -1 , -1 } ,
{ -1 , -1 , 0 , -1 , 10 } ,
{ -1 , -1 , 20 , 0 , 60 } ,
{ -1 , -1 , -1 , -1 , -1 }
};
int size = 5;
int start = 0;
int dest = 1;
int pathlen;
int path[maxPoint];
double dist;
CGraph g;
g.SetGraph( graph , start , size );
g.Display();
printf( '----------------------------------------\n' );
for( dest = 0 ; dest < size ; dest++ )
{
dist = g.GetBestWay( dest , path , pathlen );
printf( '从 %d 到 %d 的最短路径长 %.f\n' , g.GetStartPoint() , dest , dist );
printf( '所经结点为:\n' );
for( int i = 0 ; i < pathlen ; i++ )
printf( '%3d' , path[i] );
printf( '\n----------------------------------------\n' );
}
getch();
return 0;
}
////////////////////////////////////////////////////////////
// 程序说明：
// 本程序在 VC++.NET 2003 上调试通过
// 首先建立 Win32控制台应用程序，工程名为 Dijkstra
// 工程设置默认
// 添加 一般C++类 CGraph
// 填写以上内容

收起