最短路徑問題 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 32544 Accepted Submission(s): 9565Problem Description給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。Input輸入n,m，點的編號是1~n,然后是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最后一行是兩個數 s,t;起點s，終點。n和m為0時輸入結束。 (1<n<=1000, 0<m<100000, s != t)Output輸出 一行有兩個數， 最短距離及其花費。Sample Input3 2 1 2 5 6 2 3 4 5 1 3 0 0Sample Output9 11

解題步驟：
注意：map[a][b],cost[a][b]分別表示ab的路徑長度與花費

初始化操作：初始化map與cost，注意如果a=b時候為頂點到自身，因此初始化為0，其他為INF方便后面求解

輸入操作：在輸入的時候不僅存儲map與cost也要選出a、b之間路徑最短與花費最低的值，因為可以輸入數據有a、b有多條路徑直接相連接。

進入Dijkstra方法內變量與數組的定義：定義要用到的訪問數組vis[]、存兩點直接最短路徑的數組d[]、存兩點之間最小花費的數組c[]、要用到的常量Min做比較操作。

初始化最短路徑數組d[]、存兩點之間最小花費的數組c[]，遍歷map與cost求start起始點到end終止點的值，初始化完成后標記第一個start頂點已經訪問過。

第一次遍歷n個頂點，如果end終點

package com.test;import java.util.Scanner;public class Main {static int maxn = 1007;static int INF = 65535;static int start, e;static int n, m;static int[][] map = new int[maxn][maxn];static int[][] cost = new int[maxn][maxn];public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {n = sc.nextInt();m = sc.nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {map[i][j] = i == j ? 0 : INF;cost[i][j] = i == j ? 0 : INF;}}int a, b, c, d;for (int i = 1; i <= m; i++) {a = sc.nextInt();b = sc.nextInt();c = sc.nextInt();d = sc.nextInt();if (map[a][b] > c) {map[a][b] = map[b][a] = c;cost[a][b] = cost[b][a] = d;} else if (map[a][b] == c) {if (cost[a][b] > d)cost[a][b] = cost[b][a] = d;}}start=sc.nextInt();e=sc.nextInt();Dijkstra();}}private static void Dijkstra() {int v = 0,Min;int[] vis = new int[maxn];int[] d = new int[maxn];int[] c = new int[maxn];for(int i = 1;i <= n;i++) {d[i] = map[start][i];c[i] = cost[start][i];}vis[start]=1;//標記訪問過for(int i=1;i<=n;i++){ // if(vis[e]==1){//終點已經遍歷了直接跳出循環 // break; // }Min=INF;for(int j=1;j<=n;j++){//如果該頂點沒有訪問過并且if(vis[j]==0&&d[j]<Min){v=j;Min=d[j];}}vis[v]=1;//標記訪問for(int j=1;j<=n;j++){//map[v][j]表示v到j的路徑長度if(vis[j]==0&&map[v][j]<INF){if(d[j]>d[v]+map[v][j]){d[j]=d[v]+map[v][j];c[j]=c[v]+cost[v][j];}else if(d[j]==d[v]+map[v][j]){if(c[j]>c[v]+cost[v][j]){c[j]=c[v]+cost[v][j];}}}}}System.out.println(d[e]+" "+c[e]);} }

總結

以上是生活随笔為你收集整理的hdu3790最短路径问题 （Dijkstra算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。