1366 - 算法7-15：迪杰斯特拉最短路径算法
时间限制 : 1 秒
内存限制 : 32 MB
在带权有向图G中，给定一个源点v，求从v到G中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。
在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。
可将迪杰斯特拉算法描述如下：
<span style="font-family:宋体;">在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。</span>
题目输入
输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。其中n不超过50，s小于n。
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
题目输出
只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。
请注意行尾输出换行。
输入/输出样例
输入格式
4 1 0 3 0 1 0 0 4 0 2 0 0 0 0 0 1 0
输出格式
6 4 7
C语言解答
#include <stdio.h> #include <string.h> int edge[51][51],isvisited[51],n,m,s,lowcost[51]; void dijkstra(int vo){ int i,j,min,pre; isvisited[vo]=1; for (i=0;i<n;i++) { lowcost[i]=edge[vo][i]; } lowcost[vo]=0; pre=vo; for (i=1;i<n;i++) { min=100000000; for (j=0;j<n;j++) { if (isvisited[j]==0&&min>lowcost[j]) { min=lowcost[j]; pre=j; } } isvisited[pre]=1; for (j=0;j<n;j++) { if (isvisited[j]==0&&lowcost[j]>edge[pre][j]+lowcost[pre]) { lowcost[j]=edge[pre][j]+lowcost[pre]; } } } } int main(){ int i,j; // freopen("1.txt","r",stdin); while (scanf("%d %d",&n,&s)!=EOF) { memset(isvisited,0,sizeof(isvisited)); for (i=0;i<n;i++) { for (j=0;j<n;j++) { scanf("%d",&edge[i][j]); if (edge[i][j]==0) { edge[i][j]=100000000; } } } dijkstra(s); for (i=0;i<n;i++) { if (i!=s) { if (lowcost[i]==100000000) { printf("-1 "); }else{ printf("%d ",lowcost[i]); } } } printf("\n"); } // fclose(stdin); return 0; }
C++解答
#include <cstdio> #include <cstdlib> #include <stack> #include <algorithm> using namespace std; const int MAXN = 50; const int INF = 1000000000; int mat[MAXN][MAXN], min_distance[MAXN], v[MAXN]; int n, s; void dijkstra() { int i, j, k; for (i = 0; i < n; i++) { min_distance[i] = INF; v[i] = 0; } for (min_distance[s] = 0, j = 0; j < n; j++) { for (k = -1, i = 0; i < n; i++) { if (!v[i] && (k == -1 || min_distance[i] < min_distance[k])) { k = i; } } for (v[k] = 1, i = 0; i < n; i++) { if (!v[i] && min_distance[k] + mat[k][i] < min_distance[i]) { min_distance[i] = min_distance[k] + mat[k][i]; } } } } int main() { scanf("%d%d", &n, &s); for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { scanf("%d", &mat[i][j]); if (mat[i][j] == 0) mat[i][j] = INF; } } dijkstra(); for (int i = 0;i < n;i++) { if (i != s) { if (min_distance[i] < INF) printf("%d ", min_distance[i]); else printf("%d ", -1); } } puts(""); return 0; }
Java解答
import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class Main { static class Node{ public Node(int v,int w) { this.v=v; this.w=w; } int v; int w; } static class R{ public R(int vertex) { this.vertex=vertex; this.distance=Integer.MAX_VALUE; } int vertex; int distance; int number; int people; } static Comparator<R> com=new Comparator<R>() { @Override public int compare(R o1, R o2) { return o1.distance-o2.distance; } }; static Scanner scn=new Scanner(System.in); static int vertex=scn.nextInt(),start=scn.nextInt(); static List<List<Node>> G=new ArrayList<>(); static boolean[] visit=new boolean[vertex]; static R[] form=new R[vertex]; static Queue<R> pri=new PriorityQueue<>(com); public static void main(String[] args) { // 初始化 for(int i=0;i<vertex;i++) { G.add(new ArrayList<>()); form[i]=new R(i); } // 创建图 for(int i=0;i<vertex;i++) { for(int j=0;j<vertex;j++) { int w=scn.nextInt(); G.get(i).add(new Node(j, w)); } } dijstra(start); for(int i=0;i<vertex;i++) { if(i!=start) { if(form[i].distance!=Integer.MAX_VALUE) { System.out.print(form[i].distance+" "); }else { System.out.print("-1 "); } } } System.out.println(); } static void dijstra(int start) { form[start].distance=0; pri.offer(form[start]); for(int i=0;i<vertex;i++) { int u=pri.poll().vertex; visit[u]=true; for(int j=0;j<G.get(u).size();j++) { int v=G.get(u).get(j).v; int w=G.get(u).get(j).w; if(G.get(u).get(j).w!=0 &&!visit[v] && form[u].distance+w<form[v].distance) { form[v].distance=form[u].distance+w; form[v].number=form[u].number; pri.offer(form[v]); } } } } }